Fix loop in a sorted linked list

Given a Sorted linked list which has a loop (link pointer of last node is not NULL and points to some other node).

Fix the link of last node (i.e make it NULL).

Solution-1: When list does not have duplicate elements

Because its a Sorted list, the next node is greater than the previous Node. We have to find the Node whose next Node is smaller than it. That Node will be the last Node in the list.

Once we reach the last Node of the list we have to just set the link pointer of the Node to NULL.

For code, we are using the below definition of Node

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

The function that will check and fix the loop will take the head pointer (pointing to first Node in the list). bUT, There can be a case where head pointer itself need to be changed (eg. We have only one Node and its link it pointing to itself). Hence we need to take address of head pointer (in C language) or a reference to head pointer (C++):

void fixLoop(Node **head)
{
    if (head == NULL || head->link == NULL) {
      return ;
    }
    // Case where head pointer need to be changed
    if(head == head->link)
    {
        head->link = NULL;
        return;
    }
    Node *temp = head;
    while (temp->link != NULL)
    {
        if (temp->data > temp->link->data)
        {
            temp->link = NULL;
            return;
        }
          temp = temp->link;
    }
}

Solution-2: If list has duplicates

If the list can have duplicates, then the above algorithm will fail, for example: in the below list:

The above code will be infinite loop (because next node value is never less than the previous node value. If we change the condition to less-than-or-equal-to (<=), then the code will set the link of very first Node with data ==3 to NULL. This is not what we want. Hence, the solution need to be different.

This is a generic algorithm that can be applied on any linked list with a loop (not necessarily a Sorted list).

In this case we have to first detect the loop in the list. Once we have detected the loop then we can remove the loop. I am writing the Loop detection algorithm again (It is explained in detail here):

bool detectLoop(Node *head)
{
    Node* slowPtr = head;
    Node* fastPtr = head;
    while(fastPtr != NULL && fastPtr->link != NULL )
    {
        slowPtr = slowPtr->link;
        fastPtr  = fastPtr->link->link;
        if (slowPtr == fastPtr)
            return true;
    }
    return false;
}

When slowPtr == fastPtr they both points to a Node in the loop (Not necessarily the first node of the loop). Now, we have a pointer to a Node inside the loop, we can use this pointer to find the first Node of the loop and Node pointing to that Node (first Node of loop) will be the last Node of the list (Last Node of linked list whose link pointer should be NULL).

void removeLoop(Node *loopNode, Node *head)
{
    Node *firstPtr;
    Node *secondPtr;
    // Set pointer to begining of List and move it forward to find first Node which is
    //    part of the loop.
    firstPtr = head;
    while(firstPtr)
    {
        // Start a pointer from loopNode and try to reach firstPtr.
        // If we are able to reach, firstPtr is part of loop.
        secondPtr = loopNode;
        while(secondPtr->next != loopNode && secondPtr->next != firstPtr)
        {
            secondPtr = secondPtr->next;
        }
        // if we have found the first Node, break
        // else try the next node (next to firstPtr)
        if(secondPtr->next == firstPtr)
            break;
        else
            firstPtr = firstPtr->next;
    }
    // After the loop firstPtr will be pointing to the first Node in loop
    // and secondPtr will be pointing to last Node of linked list
    secondPtr->next = NULL;
}

Above algorithm is Floyd’s cycle-finding algorithm.