CareerCup

Pseudo code:
1. Two pointers start from head
2. One pointer advances one while the other advances two.
3.1 If two pointers meet, there is a loop
3.2 If pointer reachs the end, there is no loop
4. Find out how many nodes in the loop, say k.
5. Reset one pointer to the head, and the other pointer to head + k.
6. Move both pointers at the same pace, they will meet at loop starting node
7. Move one pointer till its next node is the loop starting node. It's the loop ending node
8. Set the next node of the loop ending node to fix the loop
9. Print the list

#include <stdio.h>

struct Node {
  int value;
  struct Node* next;
  Node(int v): value(v), next(NULL) {}
};

struct List {
  Node* head;
  List(): head(NULL) {}
  void push_back(Node *node) {
    if (head == NULL) {
      head = node;
      return;
    }
    Node *cur = head;
    while(cur->next != NULL) {
      cur = cur->next;
    }
    cur->next = node;
  }
};
int main()
{
  List l;
  // HEAD->1->2->3->'4'->5->6->7->'4'->5->6->7->'4'->5->6->7-> ...
  l.push_back(new Node(1));
  l.push_back(new Node(2));
  l.push_back(new Node(3));
  Node *four = new Node(4);
  l.push_back(four);
  l.push_back(new Node(5));
  l.push_back(new Node(6));
  l.push_back(new Node(7));
  l.push_back(four);
  Node *p1 = NULL, *p2 = NULL;
  while(1) {
    if (p1 == NULL && p2 == NULL) {
      // 1. Two pointers start from head
      p1 = l.head;
      p2 = l.head;
    } else {
      // 3.1 If two pointers meet, there is a loop
      if (p1 == p2)
        break;
    }
    // 3.2 If pointer reachs the end, there is no loop
    if (p2->next == NULL || p2->next->next == NULL) {
      printf("There is no loop in the list.\n");
      return 0;
    }
    // 2. One pointer advances one while the other advances two.
    p1 = p1->next;
    p2 = p2->next->next;
  }
  // 4. Find out how many nodes in the loop, say k.
  unsigned int k = 1;
  p2 = p2->next;
  while (p1 != p2) {
    p2 = p2->next;
    k++;
  }
  printf("There are %d nodes in the loop of the list.\n", k);
  // 5. Reset one pointer to the head, and the other pointer to head + k.
  p1 = l.head;
  p2 = l.head;
  for (unsigned int i = 0; i < k; i++)
    p2 = p2->next;
  // 6. Move both pointers at the same pace, they will meet at loop starting node
  while(p1 != p2) {
    p1 = p1->next;
    p2 = p2->next;
  }
  printf("node %d is the loop starting node.\n", p1->value);
  // 7. Move one of the pointer till its next node is the loop starting node.
  // It's the loop ending node
  p2 = p2->next;
  while(p2->next != p1)
    p2 = p2->next;
  printf("node %d is the loop ending node.\n", p2->value);
  // 8. Set the next node of the loop ending node to fix the loop
  p2->next = NULL;
  // 9. Print the list
  Node *cur = l.head;
  printf("The list without loop is: ");
  while(cur != NULL) {
    printf("%d ", cur->value);
    cur = cur->next;
  }
  printf("\n");
}

Output:
$ ./remove-loop-from-linked-list
There are 4 nodes in the loop of the list.
node 4 is the loop starting node.
node 7 is the loop ending node.
The list without loop is: 1 2 3 4 5 6 7

To find where the node where the loop happens:

Take 2 pointers A B. A goes 1 node each time. B goes 2 nodes each time. If they meet there is a loop.

Now make B stop at where they meet. Restart A. This time both of them go 1 node at a time. When they meet again it is where the loop happens. Just make the next pointer NULL.

Node n1 = n2 = head;
while (true) {
  n1 = n1.next;
  n2 = n2.next.next;
  if (n1 == n2) 
    break;
}
n1 = head;
while (n1.next != n2.next) {
  n1 = n1.next;
  n2 = n2.next;
}
n2.next=null

bool LoopCorrectn(nodeptr ptr)
{
nodeptr slow = ptr;
nodeptr fast = ptr;
nodeptr head = ptr;
nodeptr head2=NULL;
do
{
if(slow)
slow = slow->link;
else
return 1;

if(fast->link)
fast =fast->link->link;
else
{
return 1;

}
}while(slow!=fast);

slow=slow->link;
fast->link=NULL;
head2 = slow;

int len1 =0;
while(head)
{
len1++;
head=head->link;
}
int len2=0;
while(head2)
{
len2++;
head2=head2->link;
}
head=ptr;
head2=slow;
if(len1<=len2)
{
if(len1<len2)
{
for(int dlen =len2-len1;dlen>0;dlen--)
head2=head2->link;
}

}
else
{
for(int dlen =len1-len2;dlen>0;dlen--)
head=head->link;
}


while(head->link!=head2->link)
{
head = head->link;
head2 = head2->link;
}
head2->link=NULL;

fast->link=slow;
}

It's not clear how the linked list is implemented. Single linked list or double linked list. Suppose single linked list:
1) head->elem1->elem2->elem3->head
2) head->elem1->elem2->elem3->tail->head

pp1 described above.
pp2:
if (tail != null && tail.next != null && tail.next = head){
tail.next = null;
}

sathya is wrong ...if you take 1->2->3->4->->5->6->7
|.....|
then n1->next never equals to n2->next??????

if u take loop as 5->6->7

it doesn't seem to work when the list looks like 1->2->3->4->5>6->7->8->9->7