Plus One Linked List

Plus One Linked List

Given a number represented by a linked list, add 1 to that number and return a new linked list. For example, if the number is 2345, then it is represented as linked as shown below.

plus one linked list

When we add one to 2345 represented by the linked list, the resulting linked list looks as follows.

add 1 to linked list

Plus One Linked List: Thought process

First of all, think if there is only one node in the linked list, that means the linked list represents a single-digit number. What will do? We will add 1 to the node.val and return a new node with the sum. This is our smallest case, however, there is a catch here as well. What if the single-digit number is 9. In that case, the sum is 10 and since every node contains only a single digit of the number, we can store 0 in the new node. What happens to 1? We can treat that 1 as a carry.
Now, there are no digits present to add carry to (remember we had only one node linked list), we will create a new node and put carry in that and then linked the carry node to the previous node with 0.

add one to linked list

This is a very important case which we learned here. When you have processed all the nodes of the linked list, if the carry remains, create a new node and attach it to the head of the list. Most of the students make a mistake in this case.

How about when there is more than one node in the linked list? In that case, 1 is added to the node in the end and carry is propagated, if any, backward till head. Next question, how can you process the last node of the linked list and move backward? Well, remember how we print a linked list in the reverse order. We go deep in the linked list till the last node and use recursion unfolding to come backward. We can use the same concept. Go to the last node recursively, maintain a carry and move backward till the head. Once, you have processed head node, check if carry is non zero, if it is, creates a new node and attach it at front.

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {
    int carry = 0;


    public ListNode addOneToLinkedList(ListNode head){
        ListNode newList = addOneToLinkedListUtil(head, 1);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(newList);
            return newNode;
        }
        return newList;
    }

    public ListNode addOneToLinkedListUtil(ListNode head, int val){

        if(head == null) return null;

        if(head.getNext() == null){
            return createNode(head, val);
        }

        ListNode returnedNode = 
             addOneToLinkedListUtil(head.getNext(), val);

        ListNode newNode = createNode(head, carry);
        newNode.setNext(returnedNode);

        return newNode;
    }

    private ListNode createNode(ListNode node, int val){
        int newVal = node.getValue() + val % 10;
        carry = (node.getValue() + val) / 10;

        return new ListNode(newVal);
    }
}

The complexity of the code is O(n), we will be processing each node at least once. The tricky part is space complexity, as recursion takes implicit stack memory, the space complexity is also O(n).
This code creates a new node, what if we new list does not have to be created and we have to return the same list back. Below code implements the PlustOne such that it returns the same list back.

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {

    public ListNode addOneToLinkedList2(ListNode head){
        int c = addOneToLinkedListUtil2(head);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(head);
            return newNode;
        }
        return head;
    }

    public int addOneToLinkedListUtil2(ListNode head){

        if(head == null) return 1;
        int sum = head.getValue() 
                      + addOneToLinkedListUtil2(head.getNext());
        head.setVal(sum % 10);

        return sum / 10;
    }
}

In the next post, we will look at how to add two numbers represented by two linked lists.

If you are preparing for interview and looking for personalized coaching, please reach out to us on communications@algorithmsandme.com or book a free session with us.

Linked list implementation in Linux kernel

Linked list implementation in Linux kernel

We learned a lot about linked and solve around 30 odd problems : Linked list problems. However, the actual implementation of a linked list in Linux kernel is very different than what we learned. Let us understand how a linked list is implemented in Linux kernel and used in kernel code.

In a simple linked list, nodes contain data and point to the next node in the linked list. In other words, its the list which contains nodes which are linked. A typical example of the structure of a node of this kind of a list is:

class Node {
  private int data;
  private Node next;

  public Node (int data, int next){
      this.data = data;
      this.next = next;   
  }

  //Getters
};

However, linked lists in the Linux kernel, it’s the other way around, that is linked list is contained inside the node. This means, that there is no next pointer inside the node and each node is effectively a head node like a circular linked list. Also, it is a doubly linked list. A lot of things in one sentence!!

Linked list implementation in Kernel

Let’s understand it in detail. As said above, linked list is contained inside the node, structure of node is like this:

struct node {
 int data;
 list_head list; // list is inside the node
};

Here list_head is what defined as :

struct list_head{
  struct list_head *next, *prev;
}

See it has two pointers, essentially, making any node which contains this structure, part of a doubly linked list. The most interesting part of this kind of definition of a node is that same node can be part of multiple lists without being reallocated for each list. For example, in traditionally linked lists, if we need two linked lists: one as odd numbers and other as prime numbers, we would have to define two linked lists, one with odd numbers and other with prime numbers. With implementation provided in the Linux kernel, we can attach the same node to two lists as shown below, where an odd number which is also prime is allocated only once.

struct numbers {
 int number;
 list_head odd_numbers; // contains all odd numbers
 list_head primer_numbers; // Contains all prime numbers
};

How to access a node in list in Linux Kernel

We understood the node structure, how can we access a given node of a linked list. It was simple to do in a normal linked list as the base address of node accessible. In list implemented in Linux kernel, we have a pointer to the list_head structure in the next node and not a pointer to next node itself, as shown below.

linked list representation in linux kernel

There is a beautiful trick in C, which is used here to access the base address of the node whose list_head pointer is given. Once the base address of a node is known, accessing the node becomes similar to a normal linked list. The trick is that given a pointer to list_head in the structure; to find the base pointer of structure, find the offset at which list_head is stored in list. Once, we know the offset, (how many bytes, it is far from base address), then just subtract that offset from the absolute address of the pointer (which is given) and we get the base address. Figure explains

node representation in linked list in linux kernel

Let’s take an example, we will use structure numbers as given above. To get offset of element number in that, code is:

(unsigned long)(&((struct numbers *)0)->number)

Now, that we have offset of number and absolute address of number, we can get the base address of struct numbers as:

((struct numbers *)((char *)(pos) - \
          (unsigned long)(&((numbers *)0)->number)))

ANSI C defines the offsetof() macro in which lets you compute the offset of field f in struct s as offsetof(struct s, f). If for some reason you have to code this sort of thing yourself, one possibility is

#define offsetof(type, f) ((size_t) \
 ((char *)&((type *)0)->f - (char *)(type *)0))

Above code is not portable and some compilers may have problems with it.

There are some MACROS which are defined in the linux kernel which are useful in dealing with linked lists. Below are some examples:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
<pre>#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)-&gt;next = (ptr); (ptr)-&gt;prev = (ptr); \
} while (0)

Please refer to this file to understand various macros which are used in Linux kernel.

In next post, we will use these constructs and see how can we created a list, access it and delete a list.

Please share if there is something wrong or suggestion for improvements. Also, if you like the content, please share it.

Difference between array and linked list

Difference between array and linked list

In last post : Linked list data structure, we discussed basics of linked list, where I promised to go in details what is difference between array and linked list. Before going into post, I want to make sure that you understand that there is no such thing called one data structure is better than other. Based on your requirements and use cases, you chose one or the other. It depends on what is most frequent operation your algorithm would perform in it’s lifetime. That’s why they have data structure round in interview process to understand if you can chose the correct one for the problem.

What is an array?
Array is linear, sequential and contiguous collection of elements which can be addressed using index.

What is a linked list?
Linked list is linear, sequential and non-contiguous collection of nodes, each node store the reference to next node. To understand more, please refer to Linked list data structure.

Difference between arrays and linked list

Static Vs dynamic size

Size of an array is defined statically at the compile time where as linked list grows dynamically at run time based on need. Consider a case where you know the maximum number of elements algorithm would ever have, then you can confidently declare it as array. However, if you do not know, the linked list is better. There is a catch : What if there is a rare chance that number of elements will reach maximum, most of the time it will be way less than maximum? In this case, we would unnecessary allocating extra memory for array which may or may not be used. 

Memory allocation

An array is given contiguous memory in system. So, if you know the address of any of the element in array, you can access other elements based position of the element.

linked list vs arrays
Statically allocated contiguous memory

Linked list are not store contiguous on memory, nodes are scattered around on memory. So you may traverse forward in linked list, given node (using next node reference), but you can not access nodes prior to it.

arrays vs linked list
Dynamically allocated non-contiguous memory

Contiguous allocation of memory required sufficient memory before hand for an array to be stored, for example if want to store 20 integers in an array, we would required 80 bytes contiguous memory chunk. However, with linked list we can start with 8 bytes and request more memory as when required, which may be wherever. Contiguous allocation of memory makes it difficult to resize an array too. We have to look for different chunk of memory, which fits the new size, move all existing elements to that location. Linked list on other hand are dynamically size and can grow much faster without relocating existing elements.

Memory requirement

It’s good to have non-contiguous memory then? It comes with a cost. Each node of linked list has to store reference to next node in memory. This leads to extra payload of 4 bytes in each node. On the other hand, array do not require this extra payload. You  have to trade off extra space with advantages you are getting. Also, sometime, spending extra space is better that have cumbersome operations like shifting, adding and deleting operation on array. Or value stored in node is big enough to make these 4 bytes negligible in analysis.

Operation efficiency

We do operations of data structure to get some output. There are four basic operations we should be consider : read, search, insert/update and delete.

Read on array is O(1) where you can directly access any element in array given it’s index. By O(1), read on array does not depend on size of array.
Whereas, time complexity of read on linked list is O(n) where n is number of nodes. So, if you have a problem, which requires more random reads, array will over-weigh linked list.

Given the contiguous memory allocation of array, there are optimized algorithms like binary search to search elements on array which has complexity of O(log n). Search on linked list on other hand requires O(n).

Insert on array is O(1) again, if we are writing within the size of array. In linked list, complexity of insert depends where do you want to write new element at. If insert happens at head, then it O(1), on the other hand if insert happens at end, it’s O(n).

Insert node at start of linked list
Insert node at the tail of linked list

Update means here, changing size of array or linked list by adding one more element. In array it is costly operation, as it will require reallocation of memory and copying all elements on to it. Does not matter if you add element at end or start, complexity remains O(1).
For linked list, it varies, to update at end it’s O(n), to update at head, it’s O(1). 
In same vain, delete on array requires movement of all elements, if first element is deleted, hence complexity of O(n). However, delete on linked list O(1), if it’s head, O(n) if it’s tail.

To see the difference between O(1) and O(n), below graph should be useful.

difference between array and linked list
Complexity analysis graph

Key difference between array and linked list are as follows

  • Arrays are really bad at insert and delete operation due to internal reallocation of memory.
  • Statically sized at the compile time
  • Memory allocation is contiguous,  which make access elements easy without any additional pointers. Can jump around the array without accessing all the elements in between.
  • Linked list almost have same complexity when insert and delete happens at the end, however no memory shuffling happens
  • Search on linked list is bad.=, usually require scan with O(n) complexity
  • Dynamically sized on run time.
  • Memory allocation is non-contiguous, additional pointer is required to store neighbor node reference. Cannot jump around in linked list.

Please share if there is something wrong or missing. If you wan to contribute to website, please reach out to us at communications@algorithmsandme.com

Linked list data structure

Linked list data structure

Linked list is a very important data structure to understand as lot of problems are asked based on linked list in Amazon, Microsoft and Google interview. Today, we will understand the basics of linked list data structure and it’s implementation. 

Linked list represent linear sequence of elements. Each element connected to next element using chain of references. Another data structure which store linear sequence of items is array. There are some advantages and uses cases where linked list way of storing sequence is more efficient than array, I will cover that into next post : Arrays Vs Linked lists.

In last paragraph, I emphasized on linkedlist being linear data structure. In linear data structure, there is a sequence and order how elements are inserted, arranged and traversed. In order to go to tail of linked list, we have to go through all of the nodes.

linked list data structure
linear data structure when elements can be traversed only in one order


Non linear data structures are the ones where elements are not arranged or traversed in a specific order. One element may be connected to many others, hence we cannot traverse them in the same order every time. Example of non-linear data structure would be maps, dictionaries, trees, graphs etc.

linked list as data structure
Non  linear data structure when nodes cannot be traversed in one order always

Linked list implementation

Linked list consists of node, any number of nodes. Each node contains two things : first, value of the node, this value can be of any type, integer, string, or other user defined type. Second, a reference which points to next node in linked list. A node can be declared as follows:

typedef struct Node {
	int data;
	struct Node * next;
} Node;
Node structure
Linked list

What happens if the node is last node in linked list? At last node, next pointer of the node points to the null. It’s very important to understand this bit, as this condition will be used on almost every problem you have to solve on linked list.

Linked list is dynamic data structure. By dynamic data structure, we mean, it’s size and nature is not defined at the time of compilation, but defined at run time. Every time, a new node is added to linked list, new memory location is allocated and previous node’s next pointer will point to new node.

Operations of linked list

  • Adding node at the end of list
    There are three basic steps to add a node to linked list at end:
  1. Check if there is already a node
    1. If no, then create a new node and return it as head of linked list.
  2. If there is a node,
    1. Scan through linked list using next pointer, reach to the last node.
    2. Create a new node, and point next pointer of last node to this new node.
Node * createNode(int val){
	Node * newNode = (Node *)malloc(sizeof(Node));
	if(newNode){
		newNode->data = val;
		newNode->next = NULL;
	}
	return newNode;
}

void addNode(Node **headRef, int value){
	//create new node
	Node *newNode = createNode(value);

	//find the last node
	Node *currentNode = *headRef;
	while(currentNode && currentNode->next != NULL){
		currentNode = currentNode->next;
	}
	if(currentNode)
		currentNode->next = newNode;
	}
	else{
		//Change headRef to point to new head.
		*headRef = newNode;
	}
}

Complexity of adding a node to linked list is O(n). 

  • Insert node at head of list
    In this case too, we allocate a new node, however, this time we do not have to scan the entire list. Every time we add node to list, it’s head changes though.
  1. Check if there is already a node
    1. If no, then create a new node and return it as head of linked list.
  2. If there is a node,
    1. Create a new node, and point next pointer new node to head.
    2. Return new node as head pointer.
Node * createNode(int val){
	Node * newNode = (Node *)malloc(sizeof(Node));
	if(newNode){
		newNode->data = val;
		newNode->next = NULL;
	}
	return newNode;
}

void addNode(Node **headRef, int value){
	//create new node
	Node *newNode = createNode(value);
	newNode->next = *headRef;
	*headRef = newNode;
}

Linked list data structure problems

It’s very important to understand that linked list is a recursive data structure. Base case is a linked list with no node, represented by NULL node. Every problem on linked list can be solved using template : process one node, and then recursively process the remaining linked list.

In programming terms, linked list is divided into two parts, head and tail. The node being processed is called head and rest of the linked list is tail. Tail has the exactly same structure as the original list. 

Problems like merging linked lists, reverse a linked list, find length of linked list all can be solved using the same template of processing one node and the recursively call function on remaining node. 

Types of linked list

There are three types of linked lists :
1. Singly linked list 
Singly linked lists contain nodes with data and reference, i.e., next, which points to the next node in the sequence of nodes. The next pointer of the last node will point to null. In singly linked list you can traverse only in one direction.

singly linked list
singly linked list

2. Doubly linked list
In a doubly linked list, each node contains two links – previous, which points to the node before current node and next,  which points to next node. The previous pointer of the first node and next pointer of the last node will point to null. In doubly linked list, you can traverse it both directions. Two references adds to weight as extra memory is required.

doubly linked list
doubly linked list

3. Circular linked list
In circular linked list, next pointer of  the last node will point to the first node. A circular linked list can be both singly as well as doubly linked list.

circular linked list
Circular doubly linked list

This was all for basics of linked list, I know problems on them are hard to solve but if you look at all the problems, they boil down to one thing : understanding of node and how recursion can be used. In next posts, we will be solving many of these problems and see how we can use these basics.

Please share if there is something wrong or missing. If you are interested in contributing to website and share your knowledge with thousands of users across world, please reach out to us at communications@algorithmsandme.com

Palindrome linked list

Palindrome linked list

First of all, what is a palindrome linked list? A linked list is palindrome if you get the same output by traversing it from head to tail or tail to head. For example, below linked list is a palindrome linked list as forward traversal is same as reverse traversal : 3,4,5,5,4,3

is linked list palindrome
palindrome linked list

Where as this linked list is not palindrome for obvious reasons.

palindrome linked list
Non palindrome linked list

Given a singly linked list, find if linked list is palindrome or not.

This problem will give us more understanding on how to iterate over singly linked list as well as how to handle linked lists in recursive functions. 

If linked list is palindrome : thoughts

What will be the brute force solution for the problem? We can scan the linked first and store the output in an storage. Then we reverse the linked list, and see if order of elements is same as what was in previous traversal.

Complexity of brute force solution is O(n), however, it requires three full traversals of linked list; first forward traversal, then to reverse linked list and then reverse traversal. Also, it require additional O(n) space.

We can put half of the linked list on stack. Traverse remaining half, for each node, same time, pop the node from stack, if data is equal, move forward, else return false. If you reach the end of linked list with stack empty, linked list is palindrome. Complexity is O(n) with additional space complexity of O(n).

is linked list palindrome
Scan till middle of linked list and push all elements in stack
Now, pop the element from stack as we move in linked list. If they are equal, continue
else return false 

if linked list is palindrome
Next node is popped and compared
we reached the end of linked list and stack is empty. Hence, linked list is palindrome

What can be better? We are interested in if only half of the linked list, rest half have to be checked w.r.t to first half we they are same of not.

If we divide linked list in two halves exactly at the middle, and reverse first half, then if all the nodes from middle node to end are same as middle to start node, linked list is palindrome.

We have to reverse only half of the linked list.

We traverse linked list to find the size, then reverse half the list, traverse again to check if first half is same as latter half. You have to take middle based on the fact if size of linked list odd or even.
Actually, you can avoid calculating the size, by following the hare and tortoise algorithm to find middle of linked list. Overall complexity is O(n) with no additional space required.

Implementation

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

#define true 1
#define false 0

#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");
}

/* We are returning next node as it will be required
	in calling function */
Node * reverseList(Node *node){
    Node *current = node;
    Node *prev = NULL;
    Node *next = node;

    while(current){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

int isPalindromeList(Node *head){

    if(!(head && head->next)) return true;

    Node *current = head;
    Node *fast = head;
    Node *prev = NULL;
    Node *midNode = NULL;
    /* We are finding the middle node.*/
    while(fast && fast->next){
        fast = fast->next->next;
        /* We are saving previous node because 
		that will be end of fist list
        in case of even number of nodes */
        prev = current;
        current = current->next;
    }

    /*Check if there are odd number of nodes, if fast pointer is
	null, then there are even number of nodes,
		else it's odd number 
	*/
    if(fast){
    	midNode = current;
    	current = current->next;
    }
    
    //Let's reverse second half of list
    Node *reversedSecondHalfHead = reverseList(current);
    
    //Terminate first linked list
    prev->next  = NULL;
    
    int isPalindrome = compareTwoLinkedLists(head,
							reversedSecondHalfHead);
    
    //Reverse back second half
    current = reverseList(reversedSecondHalfHead);
    
    //If there are odd number of nodes, midNode should not be null
    if(midNode){
    	prev->next = midNode;
    	midNode->next = current;
    }
    else
    	prev->next = current;
    	
    return isPalindrome;
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s", isPalindromeList(head)
		? "true" :"false");
	return 0;
}

Is palindrome linked list : recursive solution

To check if string is palindrome, standard way is to keep two pointers (i and j), i moving from left to right and j moving from right to left.  We check if character at i and j match or not.  If they don’t match, string is not palindrome. If i and j cross each other, string is palindrome.
Can we apply above algorithm on linked list? No, because we cannot move backward in singly linked list. So what is the way? How about simulating the stack using recursive function.

We use two pointers, forward and backward, we move backward pointer ahead till we reach the end of linked list, that will be the terminal condition of recursive function. At any given time after hitting the terminal condition, forward and backward pointers will be n nodes from start and end respectively, where n varies from 0 to n.
We check if content of both pointers are equal or not, if not, then linked list is not palindrome, if yes, linked list is palindrome till those nodes.

Palindrome linked list : implementation

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

#define true 1
#define false 0

#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");
}

int isPalindromeUtil(Node **forward, Node *backward){
	//There are no nodes is lists
	if(!backward) return true;
	
	/*we are recursing moving backward pointer ahead. Backward
	pointer will start moving backward once we hit
	above terminal condition of recursion */
	int isPalindrome = isPalindromeUtil(forward, backward->next);
	
	if(!isPalindrome) return isPalindrome;
	/*At this point forward is n nodes ahead from start and
	backward n nodes away from end n varies from 0 to n 
	Compare forwad and backward
	*/
	if((*forward)->data != backward->data){
		return false;
	}
	//Move ahead forward pointer, backward will move back
	automatically due to recursion
	*forward = (*forward)->next;
	
	return isPalindrome;
}

int isPalindromeListRecursiveMethod(Node *head){
	/* we are starting with forward pointer and backward at head.
	Notice that we passing reference to forward and just pointer
	for backward pointer */
    return isPalindromeUtil(&head, head);
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 2);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s",
	    isPalindromeListRecursiveMethod(head) ? "true" :"false");
	return 0;
}

Complexity of algorithm to check if linked list is palindrome or not is O(n).

Please share if there is something missing or wrong. If you are interested in receiving study material for your interview preparation, please signup on Algorithms and Me mailing list.

Delete a given node from linked list

Delete a node from linked list

Write a program to delete a node from a linked list. For example, in the linked list shown below, if we were asked to delete node 5, the result will be the linked list as shown.

delete node from linked list

delete a node in linked list

To delete a node from the linked list, first, we need to find the node with the given value. We compare given value with the value of each node of the list; if the values match, we found the node to delete. To delete a node in a singly linked list, next pointer of the previous node of current node will point to next node of the current node. previous->next = current->next

However, if we are matching the value of the node with the given value as mentioned above, we don’t have access to the previous node of the current node.

So what shall we do? There are two ways we can solve this problem: First, we compare the value of next of the current node instead of the current node, that way we are at the previous node of the node to be deleted when the match happens. Second, keep track of the previous node while traversing the linked list forward.

The node to be deleted can be anywhere in the linked list, there are three possibilities:

  • Node to be deleted is the head node of linked list.
  • Node to be deleted is any of the middle nodes.
  • Node to be deleted is last node of linked list.
  • In the first case, we should also update head pointer of the linked list. For second and third cases, we can just change the pointers: next of the previous node points to the next of the current node).

    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<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;
            }
        }
    
        public void deleteNode(int val){
            Node current = this.head;
            Node prev = null;
    
            while(current != null && (int)current.getData() != val){
                prev = current;
                current = current.getNext();
            }
    
            //Case where node to be deleted is head
            if(current == this.head){
                this.head = this.head.getNext();
                 return;
            }
    
            if(current != null){
                prev.setNext(current.getNext());
            }
            //let the gc free the memory
        }
    
        public void printList(){
            Node current = this.head;
    
            while(current != null){
                System.out.print(" " + current.getData());
                current = current.getNext();
            }
        }
    }
    

    Delete a node from a linked list with a reference

    Above implementation will not work if there are duplicate values in a linked list, we will delete the first node with the given value and it may not be always the node intended to be deleted. What if we were given the pointer or address to the node to be deleted?

    One way is to scan through the linked list and find the node matching the pointer. We can do that by comparing current->next to the pointer given. If they are equal, we can link the current->next = givenNode->next.

    Can we avoid the traversing of the linked list? Yes, we can. We know the pointer to the node, let’s say it is givenNode. If we copy value of givenNode->next node into givenNode->value, we can delete the givenNode->next node. Before deleting the node, we will link givenNode->next = givenNode->next->next.

    delete a node from linked list

    This method will not work if the node to be deleted is the last node of the linked list. In that case, even if we avoid accessing the null node after the last node, we may not be able to touch previous node’s next pointer, which will point to a freed node once we delete the last node.

        public void deleteNode(Node nodeToDelete){
            Node current = this.head;
    
            if(nodeToDelete == null) return;
    
            if(nodeToDelete.getNext() != null){
                //Copy data
                nodeToDelete.setData(nodeToDelete.getNext().getData());
                //Change pointer
                nodeToDelete.setNext(nodeToDelete.getNext().getNext());
            }
            //let the gc free the memory
        }
    

    The complexity of both of the above algorithms to delete a node in a linked list is O(N) where N is the number of nodes in the linked list.

    Please share if there is anything wrong or missing. If you are preparing for an interview, and want to have personalized coaching to guide you through it, please signup here for free interview preparation session.

    Merge point of two linked lists

    Merge point of two linked lists

    Given two linked lists, we need to find out that if two linked list merge, if yes, find merge point.
    For example, in the figure below, node(5) is the merge point of two linked lists.

    merge point of two linked list

    How can we identify that two linked list do not merge? Easy, if two linked lists merge at any given node including the last node, the last node should be same. If the last nodes of two linked lists are different, we can safely say that two linked list do not merge.

    Merge point of two linked lists

    How to find the merge point is the next problem. From the above diagram, notice that all the nodes after merge point are same if two linked list are merged at a certain node. So that part of two linked lists is common to both.
    We can use this insight to find the merge point. If lengths of two linked lists are equal, then we can just start a traversal of those lists from heads and they will meet the merge point.

    What if the lengths are different? In this case, there is an equal number of nodes in two linked list after the merge point. The difference has to be before the merge point. If we get the difference between the lengths and move the pointer on the longer list head by the difference, we will reach the merge point at the same time when we traverse lists again.

    merge point of two linked lists

    If length of two linked lists is different, problem reduces to the problem where we need to reach at the end of two lists at the same time. There is a simple solution to that.

    Merge point of two linked lists: implementation

    #include<stdlib.h>
    #include<stdio.h>
    
    typedef struct node{
        int data;
        struct node *next;
    } Node;
    
    void print_list(Node * head){
            while(head){
                     printf("%d->" , head->data );
                     head = head->next;
            }
    
            printf("NULL");
            printf("\n");
    
    }
    
    int merge_point(Node *L1, Node *L2){
    
            Node * current1 = L1;
            Node * current2  = L2;
    
            int count_1 = 0;
            int count_2 = 0;
            //If any one list is null, return false
            if(!current1 || !current2 ) return -1;
    
            //Count number of nodes in list 1;
            while(current1->next){
                    count_1++;
                    current1 = current1->next;
            }
            // Count number of nodes in list 2
            while(current2->next){
                    count_2++;
                    current2 = current2->next;
            }
            /*If last nodes of both linked list are not same,
            linked list don't merge. */
            if(current1 != current2)
                    return -1;
    
            //Calculate the difference in lengths of linked list.
            int diff = abs(count_1 - count_2);
    
            //Move the longer linked list by diff number of nodes
            if(count_1 < count_2){
                    Node * temp = L1;
                    L1 = L2;
                    L2 = temp;
            }
            current1 = L1;
            current2 = L2;
    
            while(diff && current1){
                    diff--;
                    current1 =  current1->next;
            }
            // Now move both linked list till they meet at merge point
            while(current1 != current2){
                    current1 =  current1->next;
                    current2 =  current2->next;
            }
            return current1->data;
    }
    
    void push(Node **head, int value){
        if(*head == NULL){
            (*head) = (Node *)malloc(sizeof(Node));
            (*head)->data = value;
            (*head)->next = NULL;
        }
        else{
            Node * newNode= (Node *)malloc(sizeof(Node));
            if(newNode){
                newNode->data = value;
                newNode->next = (*head);
                *head = newNode;
            }
        }
    }
    
    void main(){
            Node * L1 = NULL;
            Node * L2 = NULL;
     		push(&L1,3);
     		Node * temp1 = L1;
            push(&L1,4);
            push(&L1,6);
            push(&L1,7);
            push(&L1,8);
            push(&L1,9);
            print_list(L1);
            printf("\n");
            push(&L2,5);
            Node * temp2 = L2;
            push(&L2,7);
            push(&L2,8);
            push(&L2,2);
            push(&L2,1);
            push(&L2,10);
            printf("\n");
    
            temp2->next = temp1;
    
            print_list(L2);
            int result1 = merge_point(L1, L2);
            if(result1 != -1){
                    printf("\n Merge Point : %d", result1);
            }
            else{
                    printf("\n Lists don't merge");
            }
    }
    

    The complexity of the algorithm to find merge point of two linked list is O(n), however, we scan the lists multiple times.

    Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching, please signup for a free demo session.

    Linked list based implementation of queue in Java

    Linked list-based implementation of queue

    A Queue is an abstract data structure which follows the First In First Out FIFO principle. It means the element which came into the queue first will leave the queue first. This ordering is very helpful in a lot of solutions. Two things are important for a queue: front and rear or tail.

    linked list based implementation of queue

    A new element is added into the queue at the rear or at the tail, which is called enqueue operation.

    queue implemented using linked list
    enqueue operation on linked list based queue

    The front is the point from where an element of a queue is taken out. This operation is called dequeue operation.

    Dequeue operation on queue implemented using linked list

    Interface for a queue would be as shown below. This interface can be implemented in multiple ways. There are different ways in which an abstract data structure can be implemented using concrete data structures, for example, a queue can be implemented using arrays or linked lists. Limitation in array-based implementation is that we have to allocate array size beforehand which restricts the number of elements that can be accommodated. Another issue is to correctly tell if the queue is empty or full. We have to maintain an extra counter for that purpose.

    package com.company;
    
    /**
     * Created by sangar on 8.10.18.
     */
    public interface Queue<E> {
        public ListNode<E> peek();
        public ListNode<E> remove();
        public ListNode<E> enqueue(E data);
        public boolean isEmpty();
        public int size();
    }
    

    Let’s discuss how to implement a queue using linked lists.

    Single linked list based implementation of queue

    A linked list a collection of nodes where each node has two components, first component store the data for the node and second component points to the next node in the linked list. In the last node, the second component points to NULL, which signifies the end of the linked list.

    singly linked list based implementation of queue
    singly linked list based implementation of queue

    If we use a linked list, we solve the first problem of statically allocating memory beforehand for the queue. The linked list is a dynamic data structure, we can allocate memory at the runtime based on our requirements. Also, to find if a queue is empty, check if linked list empty, which is a simple operation to check if the head of linked list NULL.

    The time complexity to remove an element out to the singly linked list based queue is O(1), remove the head and make the next node of the head new head. However, to add an element into the singly linked list, we have to go the end of the lists which has a time complexity of O(n).

    This problem can be easily be solved by keeping a tail pointer, which points to the last node of the linked list. When we have to enqueue an element in the queue, we update the next of tail to point to the new node and make new node has the tail of the queue. The complexity of enqueue operation is also O(1).

    The singly linked list seems to be working for the queue implementation, with dynamic size, dequeue and enqueue operation with O(1) complexity.

    One more operation performed on queues to solve certain problems like LRU Cache, non repeated characters in a stream etc. This operation is to delete a random node in queue. Given a random node in the queue, remove that node from the queue.

    This problem is tricky in a singly linked list. Brute force solution is to traverse the linked list, go till the previous node and the do the pointer rearrangement and then free the memory of the given node. This operation in the worst case requires O(n) operations. There is a trick method, which is to copy the data of the next node of the given node to the given node and then delete the next node. Caveat to this trick, which I have discussed in delete a node from linked list.

    To delete a node from a linked list, two pointers are required: the previous node of the node and the next node of the node. All we do is to make the next pointer of the previous node point to the next node of the given node and free the given node.

    Doubly linked list based implementation of queues

    From the above discussion, it is easy to guess which type of linked list implementation will give us previous and next node of a given node without traversing the list. It is doubly linked list.

    doubly linked list based implementation of queues
    doubly linked list based implementation of queues

    All the operations remain the same, with same time complexity. With the doubly linked list, delete operation also becomes O(1). So, whenever you have a use case where you may have to delete a random node from the queue, always go for the doubly linked list based implementation. The only overhead is that we have to store double the number of pointers than a singly linked list.

    package com.company;
    
    /**
     * Created by sangar on 8.10.18.
     */
    public interface Queue<E> {
        public ListNode<E> peek();
        public ListNode<E> remove();
        public ListNode<E> enqueue(E data);
        public ListNode<E> deleteNode(ListNode<E> node);
        public boolean isEmpty();
        public int size();
    }
    
    package com.company;
    
    /**
     * Created by sangar on 8.10.18.
     */
    public class QueueImplementation<E> implements Queue<E>{
        ListNode<E> head;
        ListNode<E> tail;
        int size;
    
        public QueueImplementation(){
            head = null;
            tail = null;
            this.size = 0;
        }
    
        @Override
        public ListNode<E> deleteNode(ListNode<E> node){
            if(this.isEmpty()) {
                return null;
            }
    
            if(this.head == node){
                if(this.head.getNext() != null) 
                    this.head.getNext().setPrev(null);
                this.head = this.head.getNext();
                this.size--;
                return node;
            }
    
            if(this.tail == node){
                if(this.tail.getPrev() != null)
                    this.tail.getPrev().setNext(null);
                this.tail = this.tail.getPrev();
                this.size--;
                return node;
            }
            /*
                We are deleting node in between. So following things happen
                1. If node has prev, set node.prev.next = node.next.
                2. If node has next, set node.next.prev = node.prev
            */
            if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
            if(node.getNext() != null) node.getNext().setPrev(node.getPrev());
    
            this.size--;
            return node;
        }
    
    
        @Override
        public ListNode peek() {
            if(this.isEmpty()) {
                return null;
            }
            return this.head;
        }
    
        @Override
        public ListNode remove() {
            if(this.isEmpty()) {
                return null;
            }
            /*
                We are deleting node at head. So following things happen
                1. Set temporary node point to head.
                2. Move head to next of node.
                3. Set prev of new head to NULL.
                4. Free the temp node.
              */
            ListNode<E> tempNode = this.head;
            this.head.setPrev(null);
            this.head = this.head.getNext();
    
            this.size--;
            return tempNode;
        }
    
        @Override
        public ListNode enqueue(E data) {
            if(this.isEmpty()) {
                this.head = new ListNode<E>(data);
                this.tail = this.head;
                this.size++;
                return this.head;
            }
            ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
            this.tail.setNext(newNode);
            this.tail = newNode;
    
            this.size++;
            return newNode;
        }
    
        @Override
        public boolean isEmpty() {
            return this.head == null;
        }
    
        @Override
        public int size() {
            return this.size;
        }
    }
    

    Circular linked list base implementation of queue

    Sometimes, the interviewer asks to you solve a trick question like this: Implement queue using only one pointer, either front or rear

    The correct answer to it is to use a circular linked list, where the last pointer points back to the head or front pointer. In that case, we will use only the rear pointer.

    Enqueue operation:
    We create a new node, point the next of new node to the next of tail node, make it next of the tail node and new node becomes the tail node. This whole operation is in constant time, hence the complexity of this operation is O(1).

    implementation of queue using only one pointer
    implementation of queue using only one pointer

       newNode.next=tail.next; 
       tail.next=newNode;
       tail=newNode; 
    

    Dequeue operation:

       node = tail.next //node to be removed
       tail.next =  node.next // point to the next of front node.
    

    We learned different ways to implement a queue using linked lists. Based on the requirements and constraints of the problem we choose one of the give implementations. To understand more how queues are implemented in Java, please read Queue Implementations

    Please share if there is something wrong or missing. If you are preparing for an interview and need personalized coaching to help you with preparation, please book a free session with us.

    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.