A linked list has tail joined back in to the list forming a loop. Identify the looped node. For example A->B->C->D->E->F->G->H->I-NULL, has been modified so that I's next is pointing to, let us say D. Task is to identify D. Alternatively, another question would be to find I and set it's next to NULL to correct the linked list.

Output:-

#### Approach to find a loop in a linked list

- First identify the loop (using fast and slow pointer method). Thereby identifying a node in the loop
- Find the loop length.
- Now start two pointers one at the head (first) of the list and another (second) at the node at loop length distance from head. Increment both simultaneously until they meet each other. If A is the length from head to the looped node and B is the loop length. A+B is the length of original linked list. Hence when the second moves by B+A length, the first one would have moved by A and hence they meet each other.

#### C++ program to find a loop in a linked list

#include <iostream> using namespace std; // List nodeclass class Node { public: int data; Node* next; }; // Linked list class class List { public: List() { head = NULL; tail = NULL;} ~List() {} Node* addNode(int val); void print(); Node* findJoinedNode(); Node* findJoinedNodeWithLoopLength(); private: Node* head; Node* tail; }; // Function to add a node to the list Node* List::addNode(int val) { Node* temp = new Node(); temp->data = val; temp->next = NULL; if ( tail == NULL ) { tail = temp; head = temp; } else { tail->next = temp; tail = temp; } return temp; } void List::print() { Node* temp = head; int ctr = 0; while ( (temp != NULL) && (ctr++ != 25) ) { cout << temp->data << " "; temp = temp->next; } cout << endl; } Node* List::findJoinedNode() { Node* ptr1 = head; Node* ptr2 = head; // First find the loop. while( ptr2->next != NULL ) { ptr1 = ptr1->next; ptr2 = ptr2->next->next; if (ptr1 == ptr2) break; } if (ptr2->next == NULL) { return NULL; } ptr1 = head; while (ptr1 != ptr2) { ptr1 = ptr1->next; ptr2 = ptr2->next; } return ptr1; } Node* List::findJoinedNodeWithLoopLength() { Node* ptr1 = head; Node* ptr2 = head; // First find the loop. while( ptr2->next != NULL ) { ptr1 = ptr1->next; ptr2 = ptr2->next->next; if (ptr1 == ptr2) break; } if (ptr2->next == NULL) { cout << "No loop exists!" << endl; return NULL; } cout << "loop length: "; // find the loop length. int loopLength = 0; while (ptr2->next != ptr1) { loopLength++; ptr2 = ptr2->next; } loopLength++; cout << loopLength <<endl; ptr1 = head; ptr2 = head; while (loopLength--) { ptr2 = ptr2->next; } while (ptr1 != ptr2) { ptr1 = ptr1->next; ptr2 = ptr2->next; } return ptr1; } // Test program int main() { List* list = new List(); list->addNode(1); list->addNode(2); list->addNode(3); list->addNode(4); list->addNode(5); Node* join = list->addNode(6); list->addNode(7); list->addNode(8); list->addNode(9); list->addNode(10); list->addNode(11); list->addNode(12); Node* tail = list->addNode(13); cout << "original list: " << endl; list->print(); // create a circular list. tail->next = join; cout << "After list is made circular, 25 node traversal of linked list gives: " << endl; list->print(); Node* jn = list->findJoinedNodeWithLoopLength(); if (jn != NULL) cout << "Joined node data: " << jn->data << endl; delete list; }

Output:-

original list: 1 2 3 4 5 6 7 8 9 10 11 12 13 After list is made circular, 25 node traversal of linked list gives: 1 2 3 4 5 6 7 8 9 10 11 12 13 6 7 8 9 10 11 12 13 6 7 8 9 loop length: 8 Joined node data: 6

## 0 comments :

## Post a Comment