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 : 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
*/
return false;
}

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 void insert(T data){
//If this is the first node to insert
}
else{
/* 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(){

return null;
}
else{

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
*/
return null;
}
else{
/* 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
*/
return null;
}

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);

//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.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/

@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
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
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.

## 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 a telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as a solution. Given two linked lists as following,

Result should be like this:

Consider the 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, whichever 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.

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
```

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

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.

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)`

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.

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.

## Merge 2 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 */
Node * newNode  = createNode(data);
}

}

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

if (list1->data < list2->data) {
} else {
list2 = list1;
}

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;
}
list1 = list1->next;
}
if (!list1->next) list1->next = list2;
}
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.

```#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 */
Node * newNode  = createNode(data);
}

}

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.

Given two linked lists, where linked list represents a big number and each node of linked list contains one digit of the number. Problem is to add two numbers represented by linked lists. The result should be stored in a third linked list. It should be noted that the head node contains the most significant digit of the numbers.

For example. let’s say we have been given two numbers: 12563 and 56743 and we have to add them. Two linked lists which will represent these numbers are as shown below.

This problem is very easy to solve if the order of the digits stored in the linked list is reversed. Look at the code given at leetcode.

``` public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry =0;

ListNode p1 = l1, p2 = l2, p3=newHead;

while(p1 != null || p2 != null){
if(p1 != null){
carry += p1.val;
p1 = p1.next;
}

if(p2 != null){
carry += p2.val;
p2 = p2.next;
}

p3.next = new ListNode(carry%10);
p3 = p3.next;
carry /= 10;
}

if(carry==1)
p3.next=new ListNode(1);

}
```

However, linked lists are not stored in reversed order and basic mathematics tells us that addition starts from the least significant digit. To access least significant digit of the numbers, we will visit the last nodes of both the lists and add them up, create a new node to store the result, take care of the “carry” if any.

Next, we go to the second to last node and do the same. Link the result node to the result node which was created when we added the last nodes.

This will continue  backwards till we reach head of one the list. Once, we reach head of a linked list, we just add all the nodes of the remaining list to the result.

It is clear that we go to the end of the lists and move back one node at a time. Actually, this is a reverse traversal of a linked list, which can easily be done with recursion, function call stack will automatically store previous nodes. However, we need to take into account the difference in the number of digits in two number and hence the difference in length of the two lists.

So before starting recursion, calculate the size difference and move the longer list pointer to appropriate place so that we reach the last node of both lists at the same time.

Another thing is to take care of is carry. If two digits add more than 10, forward the carry to the next node and add it to it. If most significant digit addition results in a carry, create an extra node to store carry.

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

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

int length( Node * head ){
int len = 0;
while(current){
len++;
current = current->next;
}
return len;
}

Node * createNode(int value){

Node * newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;

return newNode;

}

Node *newNode = createNode (value);
}
else{
}
}
/* This function is actually helper function
which does all house keeping like calculating
lengths of lists,calling recursive implementation,
creating extra node for carry in MSD,
and adding any remaining nodes left in longer list. */

/* result is pointer to pointer to the head of resulting node */
void addTwoNumbers(Node *L1, Node *L2, int *carry, Node  **result)
{
int len1 = length( L1 );
int len2 = length( L2 );
int diff = 0;

if(len1 < len2){
Node * current = L1;
L1 = L2;
L2 = current;
}
diff = abs(len1-len2);
Node * current = L1;

while(diff--)
current = current->next;

/* Call the recursive implementation */

diff = abs(len1-len2);

/* Add remaining nodes in longer list */

if(*carry){
push(result, *carry);
}
return;
}
int *carry, Node **result){

int sum;
if(!L1)
return;

/*We have reached the last node of both lists, add them */
sum = L1->data + L2->data + (*carry);

int value = sum%10;
*carry = sum/10;
push(result, value);

return;
}
Node **result, int diff){
int sum =0;

if(!L1 || !diff)
return;

sum = L1->data + (*carry);
int value = sum%10;
*carry = sum/10;

push(result, value);

return;
}

void printList( Node * head ){
while(current){
printf("%d ->", current->data);
current = current->next;
}
printf("NULL");
}
/* 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,3);
push(&L1,4);
push(&L1,6);
push(&L1,7);
/* creating list 2 */
push(&L2,8);
push(&L2,9);
push(&L2,7);

printList(L1);
printf("\n");
printList(L2);