Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf

Merge two sorted linked lists

Merge two sorted linked lists

Problem statement is simple : Merge two sorted linked lists, without using extra space. To refer to the basics of linked list, please follow the post : Linked list data structure. This problem is commonly asked in telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as solution. Given two linked lists as following,

merge two sorted linked lists
Two sorted linked lists

Result should be like this:

merge two sorted linked list
Resultant linked list.

Merge two sorted linked lists : Thoughts

Consider following two steps to merge sorted linked lists. First, figure out which node should be head of result list. Compare head nodes of two give lists, which ever is smaller, that should be the head of result list.

Second, compare two nodes, one from each list and decide which should go next in result linked list.  Advance the pointer to next node of the node which is added to result list.

As no new node is allocated during this merge, we have to make sure that all the references are maintained when nodes are added to merged linked list.

merge two sorted linked list
Two sorted list to be merged

We can start with one list as merge list and add nodes from second list at appropriate place in that list. Let’s say L1 is our merged list and we always compare node on L2 to see if it should be placed in L1 at current position. L1 grows as more nodes are sorted in merge list.

We compare first two nodes L1 and L2, and decide that node(2) has to go in merged list as head. If it was head of L2, we would have swapped L1 and L2 heads and still L1 will be head of merged list. Why? Because we want that L1 always points to last node in merged list and L1 to represent sorted merged list till this point and L2 switches between two input lists.

As L1 always points to the last node of merged linked list, next node to compare should be L1.next i.e node(4) and L2 i.e node(3).

As L1 follows the merged linked list, we will move L1.next to point node(3), however doing it directly will lead to lose of entire linked list following it. So we do it in four steps : store L1 next as temp; link L2 to L1.next; L2 points to temp and then move L1 to L1.next

Node temp = L1.next;
L1.next = L2;
L2 = temp;
L1 = L1.next
merge two sorted linked lists

Next nodes to be compared are node(5), which is L1.next and node(5) which is L2.

Comparing node 4 and 5 to add in sorted merge list

Of course node(4) has to be added to merged linked list, what should we do? First save L1.next in temp, temp now points to node(5). Second, point L1.next to L2, point L2 to temp, and at last, L1 moves to L1.next. State of two sorted linked lists looks as follows.

merge two sorted linked lists

By this time you must have noticed that L1 and L2 do not point to the one list all the time, L1 always points to the last node of merged list and L2 points to first node of separated list which needs to be merged.

Now, L1.next which is node(7) and L2 which is node(5) will be compared.

node(5) is to be added in merged sorted list. Again same set of steps. L1.next stored as temp, L1.next points to L2 i.e. node(5) and then L2 points to temp i.e. node(7)

merge two sorted linked lists

Again, node(9) which is L1.next will be compared to L2 i.e node(7). L1.next should point to L2. Final state will be as follows

At this point, L1.next i.e node(8) is less than L2, this is simple case, where we just move L1 to L1.next and L2 remains as is.

merge two sorted linked lists

Next two nodes follow the same pattern and added to merged sorted linked list.

At this point, special condition occurs which is L1.next is null. In this case, point L1.next to L2 and two linked lists are merged.

Two sorted linked lists are merged into a sorted list

Merge two sorted linked lists : Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}
Node * MergeLists(Node *list1, Node *list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  Node *head;
	//Chosing head of merged list
  if (list1->data < list2->data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
	
  while(list1->next && list2) {
    if (list1->next->data > list2->data) {
	//Step 1. Save the next pointer
      Node *tmp = list1->next;
	//Step 2. Change next pointer to point L2
      list1->next = list2;
	//Step 3. Move L2 to temp
      list2 = tmp;
    }
	//Step 4. Move L1 ahead
    list1 = list1->next;
  } 
  if (!list1->next) list1->next = list2;
  return head;
}
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
	
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = MergeLists(L1,L2); 
        printList(L1);
 
        return 0;
}

Complexity of this method to merge two sorted lists into one is O(n+m) where n and m are number of nodes in two sorted linked lists.

Recursive implementation to merge two sorted linked lists

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(a ==  NULL)
        return b;
    else if(b == NULL)
        return a;

    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = mergeSort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = mergeSort(a,b->next);
      }
      return result;
}

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}

/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
      
        L1 = mergeSort(L1,L2); 
        printList(L1);
        
        return 0;
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for free demo class.