Removing a loop in a singly linked list

Problem:
Remove a loop from a singly linked list if the list has a loop.

Example
For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4.

Solution 
 The problem has 3 steps :

1. Detect if there is a loop in the list (already solved here)
2. Identify the start of the loop (already discussed here)
3. Delete the loop, which we will discuss here. Please go through 1 and 2.

Once you know where the loop starts, it's easy to identify the last element in the list since it's the element in the list following the start of the loop that ends up pointing back to the start of the loop. It is then trivial to set the next pointer/reference of this element to null to correct the cyclic link list (not circular linked list which is where the last elements points back to the first - this would be a specific instance of cyclic lists).

1. Floyd's cycle detect algorithm, also called the tortoise and hare algorithm as it involves using two pointers/references that move at different speeds, is one way of detecting the cycle. If there is a cycle, the two pointers (say p1 and p2) will end up pointing to the same element after a finite number of steps. Interestingly, it can be proved that the element at which they meet will be the same distance to the start of the loop (continuing to traverse the list in the same, forward direction) as the start of the loop is to the head of the list. That is, if the linear part of the list has k elements, the two pointers will meet inside the loop of length m at a point m-k from the start of the loop or k elements to the 'end' of the loop (of course, it's a loop so it has no 'end' - it's just the 'start' once again). And that gives us a way to find the start of the loop:
2. Once a cycle has been detected, let p2 remain pointing to the element where the loop for the step above terminated but reset p1 so that it's pointing back to the head of the list. Now, move each pointer one element at a time. Since p2 began inside the loop, it will continue looping. After k steps (equal to the distance of the start of the loop from the head of the list), p1 and p2 will meet again. This will give you a reference to the start of the loop.
3. It is now easy to set p1 (or p2) to point to the element starting the loop and traverse the loop until p1 ends up pointing back to the starting element. At this point p1 is referencing the 'last' element list and it's next pointer can be set to null.
   

Here is the C++ implementation of the algorithm:

struct Node
{
  int data;
  Node* next;
};

void removeLoop(Node* head)
{
  if (head == NULL)
    return;

  Node* slow = head;
  Node* fast = head;
  Node* last = NULL;
  
  bool hasLoop = false;

  while (fast->next != NULL && fast->next->next != NULL) 
  {
    last = slow;
    slow = slow->next;
    fast = fast->next->next;
    
    if (slow == fast)
    {
      hasLoop = true;
      break;
    }
  }

  
  if (hasLoop)
  {
    slow = head;

    while (slow->next != fast->next)
    {
      slow = slow->next;
      fast = fast->next;
    }
    
    if (slow == head && fast == head )
      last->next = NULL;
    else
      fast->next = NULL;
  }
}

Explanation: our method takes only the reference to the list's head node as an argument. The first while loop determines if the list has loop. And, the second while loop points the loop's end node to null, terminating the loop:

1. If the list is empty (head points to NULL), there is nothing to do so return.
2. Next, we need three different pointers. slow will go through the list one node after another. fast moves through the list two nodes at a time, so it goes twice as fast as the slow pointer. And, last refers to the previous node visited by the slow pointer.
3. We just have to loop through the list until fast reaches NULL because if the linked list doesn't have loop, fast will reach NULL eventually. Moreover, if the list does have a loop, we'll break out of the while loop immediately.
4. As the while loop runs, we check if slow and fast pointer point to the same node. When they do, it means the list has a loop. This is a very common technique to find out if a linked list has loop. Here is a post about that technique if you are not familiar with it.
5. As soon as we know that the list has loop, we set the flag hasLoop to true. And then, we break out of the while loop immediately because fast will never reach NULL and the while loop will never end.
6. If the list has loop as indicated by the flag hasLoop, we enter the second while loop to remove that the list's loop.
   
   a) First, we set the slow pointer back to the list's head node.
   
   b) Then, we move both the slow and fast pointer one node at a time. They will eventually meet each other because the list still has a loop.
   
   c) We stop the loop right before the pointers meet. That's how we get the reference to the end node of the loop:
   
   d) If the slow and fast pointer both point to the head of the list, then the list is circular, meaning that the end node points back to the head node of the list (ie. 1->2->3->4->1). Thus, we'll get the reference to the end node by using the last pointer. Remember that last is pointing to either the head of the list or the end node of the loop after the first while loop. That's why if slow and fast point at the head, then slow must be pointing at the end node.
   
   e) On the other hand,if the end node is pointing to any node in the list other than the head node (ie. 1->2->3->4->2), then slow and fast is pointing to the end node and last is pointing to the head node. Thus, we use fast pointer instead of last pointer to break the loop.
   
   

This algorithm takes O(n) time complexity and O(1) space complexity. It's very efficient!!

Read More

Y – shaped Linked List. Algorithm to find the node of intersection of two lists.

Problem

Find the node of intersection of 2 lists.

Example:

Solution

Method 1 - Taking advantage of the link list length
Here is the pseudo code to find the node of intersection of 2 lists:

1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list
       ( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node 
   When the 2 nodes are pointing to same node, we found our merge node.

Java code

public static <T> int length(ListNode<T> listHead){
  int listLen = 0;
  ListNode<T> current = listHead;
  while (current != null)
  {
   listLen++;
   current = current.next;
  }
  return listLen;
 }

 public static <T> ListNode<T> 

firstCommonNode(ListNode<T> pList1,ListNode<T> pList2)
 {
  int length1 = length(pList1);
  int length2 = length(pList2);
  
  if (length1 > length2)
  {
   for (int a=0; a < (length1-length2); a++)
   {
    pList1 = pList1.next;
   }
  }
  else
  {
   for (int a=0; a < (length2-length1); a++)
   {
    pList2 = pList2.next;
   }
  }
  while (pList1 != pList2)
  {
   pList1 = pList1.next;
   pList2 = pList2.next;
  } 
  return pList1;
 }

Explanation:
Our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:

First while loop counts the number of nodes in the first list.
Second while loop counts the number of nodes in the second list.
After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.

You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?

Time complexity - O(m+n)
Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).

Method 2 - Create the loop in Y shaped list
 Here is the pseudocode

1)traverse the first list and reach at the end
2)link the end of first list to the head of second list
3) Retain the pointers at the head of both list,also at the end of 1st list
4) Now we have a loop in the linked list, see the image. 
       and we have to find the start of loop, which is 3 in example
5)Take two pointers move 1st by one node,second by two
6) when they meet after that take back the 1st to head
7)Now move both pointers 1st and second also by one node(from the meeting point)
8)where they meet is the intersection of both list
9)break the link from last of 1st list to head of second

You can read on finding the loops in LL here, and eventually method to find the start of the loop.

Read More

Finding the Start of a Loop in a Linked List

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/linked-list-cycle-2-find-start-of-a-cycle/.

Problem 

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
Circular linked list:
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

Example

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

Answer here is 3.

Solution
The problem here is 2 fold - First check if there is any loop or not, if the loop is present , we can simply find the loop in O(n) time.

We can find the loop in the linked list via Floyd’s Cycle-Finding Algorithm, explained here.

The algorithm is pretty straightforward:

1. We start at the beginning of the linked list with two pointers.
   
2. The first pointer is incremented through each node of the list. The second pointer moves twice as fast, and skips every other node.
   
3. If the linked list contains a loop, these two pointers will eventually meet at the same node, thus indicating that the linked list contains a loop. 

Consider the linked list :

>head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

Incrementing pointers A at rate of 1 and B at 2, they take on the following values:

A   B
1   6
2   7
3   8
4   8
5   4
6   6

Method 1 - Increment the Hare pointer by loopsize

Now we can see that loop is there, as A and B meet at 6 :

                                 AB (this is where A and B
                                 |               first met).
                                 v
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

• First, advance B and set the loopsize to 1.
• Second, while A and B are not equal, continue to advance B, increasing the loopsize each time. That gives the size of the loop, six in this case. If the loopsize ends up as 1, you know that you must already be at the start of the loop, so simply return A as the start, and skip the rest of the steps below.
• Third, simply set both A and B to the first element then advance B exactly loopsize times (to 7 in this case). This gives two pointers that are different by the size of the loop.
• Lastly, while A and B are not equal, you advance them together. Since they remain exactly loopsize elements apart from each other at all times, A will enter the loop at exactly the same time as B returns to the start of the loop. You can see that with the following walkthrough:
  
  • loopsize is evaluated as 6
  • set both A and B to 1
  • advance B by loopsize elements to 7
  • 1 and 7 aren't equal so advance both
  • 2 and 8 aren't equal so advance both
  • 3 and 3 are equal so that is your loop start

Now, since each those operations are O(n) and performed sequentially, the whole thing is O(n^2).

Method 2 - Iterate from first pointer and see if nodes are reachable
We know that Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the above diagram). We store the address of this in a pointer variable say ptr2. Then we start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. When we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get pointer to the previous of this node.

Method 3  - Efficient O(n) solution

Once a loop has been found, the following additional steps will give us the starting node of the loop:

• Once a cycle has been detected, let B remain pointing to the element where the loop for the step above terminated but reset A so that it's pointing back to the head of the list. 
• Now, move each pointer one element at a time. Since B began inside the loop, it will continue looping. After k steps (equal to the distance of the start of the loop from the head of the list), A and B will meet again. This will give you a reference to the start of the loop.

To sum it up:
This method is also dependent on Floyd’s Cycle detection algorithm.

1. Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2. Count the number of nodes in loop. Let the count be k.
3. Fix one pointer to the head and another to kth node from head.
4. Move both pointers at the same pace, they will meet at loop starting node.
5. Get pointer to the last node of loop and make next of it as NULL.

So here once loop is detected :

                                 AB (this is where A and B
                                 |               first met).
                                 v
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

We move A to start. Now we increment each by 1 till they meet:

A   B
1   6
2   7
3   8
4   3
5   4
6   6

This algorithm isn’t too difficult compared to the algorithm for detecting a loop. However, the mental model seems a bit trickier. Why and how does it always find the start of the loop?

How does the Algorithm work? An intuitive explanation:

Here’s some explanation which would hopefully help you intuitively understand why the algorithm works, without going into a lot of mathematical detail.
First, meeting point of two pointers in a loop
Consider two pointers: a slow pointer S that increments by one node at each step, and a fast pointer F that increments by two nodes at each step (i.e. it is twice as fast as S). Both pointers start at the same time from the beginning of an n-node loop. In the time S covers n nodes. F will have covered 2n nodes and they will both meet at the start of the loop.
Now, let us say that the slow pointer S starts at the beginning of the loop, and the fast pointer F starts at node k (where k < n) of the loop. As these two pointers move along the loop, they will meet at node (n-x).
What we really need to do is figure out x, as it will give us the node at which the two pointers meet inside the loop.

1. When S takes n/2 steps, it will be at node n/2. During the same time, F will have taken 2(n/2) = n steps, and it will be at node (k+n). Since the we are inside a loop, F will be effectively back at node k.
   
2. In order for the two pointers to meet at node (n-x), S needs to take a further (n-x-n/2)=(n/2-x) steps and it will end up at node n-x. During the same time, F will have taken 2*(n/2-x)=(n-2x) steps and will be at node k+(n-2x). Given our assumption that both S and F meet at the same node:

n-x = k+n-2x
=>   x = k

This means that if S starts from the start of the loop, and F starts k nodes into the loop, both of them will meet at node (n-k), i.e k nodes from the end of the loop. This is a key insight.

Circular Linked List
Now, coming back to the linked list that contains a loop. Suppose the start of the loop is m (e.g. m=3) nodes from the start of the linked list. Both S and F start at the beginning of the linked list [Figure-1].

By the time S gets to node m (i.e. start of loop), F will be at node 2m [Figure-2]. This means that S will be at the start of the loop and F will be m nodes *into the loop*.

Based on the discussion above, we already know that if S begins from the start of the loop and F starts from node m, they will meet m nodes from the end of the loop (i.e. the orange-node in [Figure-3]).

At this point, keep the pointer F at the orange-node where the two pointers met (i.e. m-nodes from the start of the loop), and move the pointer S to the beginning of the linked list [Figure-4]. Now, if we increment both S and F *one node at a time*, it is obvious that they will meet at ‘Node-m’ (red-node) of the list, which is the start of the loop.

Source code:

/**
 * Returns the node at the start of a loop in the given circular linked
 * list. A circular list is one in which a node's next pointer points
 * to an earlier node, so as to make a loop in the linked list. For
 * instance:
 *
 * input: A -> B -> C -> D -> E -> C [the same C as earlier]
 * output: C
 *
 *
 * @param linkedList
 *            list to be tested
 * @return the node at the start of the loop if there is a loop, null
 * otherwise
 */
public static IntegerNode findLoopStart(LinkedList linkedList) {
 if (linkedList == null || linkedList.getHead() == null) {
  return null;
 }

 IntegerNode loopStartNode = null;
 IntegerNode slow = linkedList.getHead();
 IntegerNode fast = linkedList.getHead();

 while (slow != null && fast != null) {
  slow = slow.getNext();
  if (fast.getNext() == null) {
   loopStartNode = null;
   break;
  }
  fast = fast.getNext().getNext();

  // If slow and fast point to the same node, it means that the
  // linkedList contains a loop.
  if (slow == fast) {

   slow = linkedList.getHead();

   while (slow != fast) {
    // Keep incrementing the two pointers until they both
    // meet again. When this happens, both the pointers will
    // point to the beginning of the loop
    slow = slow.getNext(); // Can't be null, as we have a loop
    fast = fast.getNext(); // Can't be null, as we have a loop
   }

   loopStartNode = slow;
   break;
  }
 }

 return loopStartNode;
}

Thanks. Some related problem to this will be delete this loop, which you can see here.

References

• Diagrams borrowed from -  http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/
• http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/

Read More

Detecting a loop in a linked list

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/linked-list-cycle-1-detect-cycle/.

Problem : Given a singly linked list, find if there exist a loop.

Example
A -> B -> C -> D -> E -> C [ E again point to C]

Solutions
Method 1 - Using hashing
Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.

Method 2 - Visited flag
This solution requires modifications to basic linked list data structure.  Have a visited flag with each node.  Traverse the linked list and keep marking visited nodes.  If you see a visited node again then there is a loop. This solution works in O(n) but requires additional information with each node.
A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash.  Just store the addresses of visited nodes in a hash and if you see an address that already exists in hash then there is a loop.

Method 3 - Floyd’s Cycle-Finding Algorithm i.e. Using 2 pointers

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.This is also called tortoise and hare approach.

Here is some code

p=head;
q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
    //Loop detected!
    exit(0);
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}

// No loop.

Time Complexity: O(n)
Auxiliary Space: O(1)

Dry running the code

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
                  ^                        |
                  |                        |
                  +------------------------+

Starting A at 1 and B at 2, they take on the following values:

A   B
=   =
1   2
2   4
3   6
4   8
5   4
6   6

Note that there is no reason that you need to use the number two. Any choice of step size will work (except for one, of course). See the proof here.


How this work - intuitive approach
Consider two pointers: a slow pointer S that increments by one node at each step, and a fast pointer F that increments by two nodes at each step (i.e. it is twice as fast as S). Both pointers start at the same time from the beginning of an n-node loop. In the time S covers n nodes. F will have covered 2n nodes and they will both meet at the start of the loop.
Now, let us say that the slow pointer S starts at the beginning of the loop, and the fast pointer F starts at node k (where k < n) of the loop. As these two pointers move along the loop, they will meet at node (n-x).
What we really need to do is figure out x, as it will give us the node at which the two pointers meet inside the loop.

1. When S takes n/2 steps, it will be at node n/2. During the same time, F will have taken 2(n/2) = n steps, and it will be at node (k+n). Since the we are inside a loop, F will be effectively back at node k.
2. In order for the two pointers to meet at node (n-x), S needs to take a further (n-x-n/2)=(n/2-x) steps and it will end up at node n-x. During the same time, F will have taken 2*(n/2-x)=(n-2x) steps and will be at node k+(n-2x). Given our assumption that both S and F meet at the same node:

  n-x = k+n-2x
 =>   x = k

This means that if S starts from the start of the loop, and F starts k nodes into the loop, both of them will meet at node (n-k), i.e k nodes from the end of the loop. This is a key insight.

Once you know a node within the loop, there's an O(n) guaranteed method to find the start of the loop. The solution is discussed here.

 But can we do better, and answer is yes.

Method 4 - Floyd’s cycle-finding algorithm (modified by Richard Brent)

Richard Brent described an alternative cycle detection algorithm, which is pretty much like the hare and the tortoise [Floyd's cycle] except that, the slow node here doesn't move, but is later "teleported" to the position of the fast node at fixed intervals.
The description is available here : http://www.siafoo.net/algorithm/11 Brent claims that his algorithm is 24 to 36 % faster than the Floyd's cycle algorithm. O(n) time complexity, O(1) space complexity. (Courtesy)

public static boolean hasLoop(Node root){
    if(root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while(slow.next != null && fast.next != null){
        fast = fast.next;
        taken++;
        if(slow == fast) return true;

        if(taken == limit){
            taken = 0;
            limit <<= 1;   // equivalent to limit *= 2;
            slow = fast;  // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

Method 5 - Reverse a list
If there are no requirements on using extra memory and keeping the list in its original state very neat and simple approach can be uses. The idea is based on the fact that if you reverse the list which has loops you will end-up on the head node while if list doesn’t have loops you will stop at the tail.

public bool hasLoop(Node head)
{
  Node first=null;
  Node second=null;
  Node tmp=head;

  while(tmp) {
     first=second;
     second=tmp;
     tmp=tmp.Next;

     if(tmp==head)
            return true;

     second.Next=first; 
  }

  return false;
} 

Once detecting the loop, we may like to find the start of the loop or delete it.


References

• stackoverflow, 
• geeksforgeeks
• http://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list

Read More