How to merge two sorted linked list in third linked list - Iterative and recursive approach

byNikhil Ranjan •
1
Problem Statement :- Given two sorted linked list, merge two linked list and form third sorted linked list containing all elements of given liked list. Solve using non-recursive and recursive approach. 
/*  Merge two sorted linked lists and form third sorted linked list
   *List1: 4-->5-->12 -->24 -->83
   *List2: 8-->9-->14 -->21 -->31 -->132 -->136
   * Result(Sorted list) : 4->5->8->9->12->14->21->24->31->83->132->136 
*/

Non-recursive approach(Iterative):-  

Iterative Since all elements are sorted in both linked list, we can traverse both liked list and by comparing element of both linked list we can decide which is smaller and put that in result linked list and repeat this until all elements are covered in one of the list and after that just copy all elements from second list.
Algorithm:-  Lets consider head1 and head2 are referring first node of two linked list.
1. Traverse linked list List1 and List2 until head1 is null or head 2 is null.
2. Compare data of first node of both list - add node with lesser value into result linked list and increment head of that linked list.
3. Repeat step 2 and move corresponding head.
4. Once head of one of list has reached at end of list, just copy all elements from another linked list into result list.

Sample code to merge two sorted linked list into one linked list (Non-recursive approach):-
private Node mergeSortedLinkedListIterative(Node head1, Node head2) {
 Node resultHead = null;
 /* Traverse both list until reaches at end of any one of list */
 while (head1 != null && head2 != null) {
  if (head2.data < head1.data) {
   resultHead = createAndAppendNodeInResultList(resultHead,
     head2.data);
   head2 = head2.next;
  } else {
   resultHead = createAndAppendNodeInResultList(resultHead,
     head1.data);
   head1 = head1.next;
  }
 }
 // Copy remaining linked list data into result list
 if (head1 != null) {
  while (head1 != null) {
   createAndAppendNodeInResultList(resultHead, head1.data);
   head1 = head1.next;
  }
 } else if (head2 != null) {
  while (head2 != null) {
   createAndAppendNodeInResultList(resultHead, head2.data);
   head2 = head2.next;
  }
 }
 return resultHead;
}
Explanation:- In while loop, both list is traversed until reaches at end of one list and compare which list node has lesser value element, if head1 refer to lesser value node, it is added in result list and head1 moves to next node. Similarly, if head2 node refer lesser value it is added and moves to next node. After while loop is exit, which ever list has more elements to be traversed is copied to result linked list.
Time and space complexity :- Since each element is traversed only once so time complexity is order of O(p+q), p and q are length of linked list. Space complexity is constant O(p+q) , length of result list.

Using recursion:-

Algorithm:- 1. Check head of both list , if one of them is null returns others, because that list does not have more elements.
2. Next, if both are non- null, check for node with lesser value and assume that node as head of result liked list. Call same method recursively with next element of that list. Do the same if other list has lesser values node.
3. Return head of result linked list.

Sample code to merge two sorted linked list into one linked list (Recursive approach):-
private Node mergeSortedLinkedListRecursive(Node head1, Node head2) {
 Node returnNode = null;
 if (head1 == null && head2 != null)
  return head2;
 if (head2 == null && head1 != null)
  return head1;

 if (head1.data < head2.data) {
  returnNode = head1;
  returnNode.next = mergeSortedLinkedListRecursive(head1.next, head2);
 }
 if (head1.data > head2.data) {
  returnNode = head2;
  returnNode.next = mergeSortedLinkedListRecursive(head1, head2.next);
 }
 return returnNode;
}

Time and space complexity :- Since each element is traversed only once so time complexity is order of O(p+q), p and q are length of linked list. Space complexity is constant O(p+q) , length of result list.
Below is complete sample program to merge two sorted linked list in third linked list(Both non-recursive and recursive approach) :-
package com.devinline.linkedlist;

public class MergeTwoSortedLinkedList {

 private Node mergeSortedLinkedListIterative(Node head1, Node head2) {
  Node resultHead = null;
  /* Traverse both list until reaches at end of one list */
  while (head1 != null && head2 != null) {
   if (head2.data < head1.data) {
    resultHead = createAndAppendNodeInResultList(resultHead,
      head2.data);
    head2 = head2.next;
   } else {
    resultHead = createAndAppendNodeInResultList(resultHead,
      head1.data);
    head1 = head1.next;
   }
  }
  // Copy remaining linked list data into result list
  if (head1 != null) {
   while (head1 != null) {
    resultHead = createAndAppendNodeInResultList(resultHead,
      head1.data);
    head1 = head1.next;
   }
  } else if (head2 != null) {
   while (head2 != null) {
    resultHead = createAndAppendNodeInResultList(resultHead,
      head2.data);
    head2 = head2.next;
   }
  }
  return resultHead;
 }

private Node mergeSortedLinkedListRecursive(Node head1, Node head2) {
 Node returnNode = null;
 if (head1 == null && head2 != null)
  return head2;
 if (head2 == null && head1 != null)
  return head1;

 if (head1.data < head2.data) {
  returnNode = head1;
  returnNode.next = mergeSortedLinkedListRecursive(head1.next, head2);
 }
 if (head1.data > head2.data) {
  returnNode = head2;
  returnNode.next = mergeSortedLinkedListRecursive(head1, head2.next);
 }
 return returnNode;
}

 private Node createAndAppendNodeInResultList(Node head, int data) {
  return head = insertLast(head, data);
 }

 private Node createNewNode(int data) {
  return new Node(data);
 }

 /* Iterate linked list, reach at end and add new node */
 private Node insertLast(Node head, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else {
   while (current.next != null) {
    current = current.next;
   }
   current.next = newNode;
   newNode.next = null;
  }
  return head;
 }

 /* Display data of nodes/iterate linked list */
 private void diplayList(Node head) {
  Node current = head;
  System.out.print(" [ ");
  if (head != null) {
   while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
   }
   System.out.print(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 class Node {
  public int data;
  public Node next;

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

 public static void main(String[] args) {
  Node head1 = null;
  Node head2 = null;
  MergeTwoSortedLinkedList mll = new MergeTwoSortedLinkedList();
  /* First linked list fomation */
  Node node1 = mll.new Node(4);
  head1 = node1;
  Node node2 = mll.new Node(5);
  Node node3 = mll.new Node(12);
  Node node4 = mll.new Node(24);
  Node node5 = mll.new Node(83);
  head1.next = node2;
  head1.next.next = node3;
  head1.next.next.next = node4;
  head1.next.next.next.next = node5;

  /* Second linked list fomation */
  Node node12 = mll.new Node(8);
  head2 = node12;
  Node node22 = mll.new Node(9);
  Node node32 = mll.new Node(14);
  Node node42 = mll.new Node(21);
  Node node52 = mll.new Node(31);
  Node node62 = mll.new Node(132);
  Node node72 = mll.new Node(136);
  head2.next = node22;
  head2.next.next = node32;
  head2.next.next.next = node42;
  head2.next.next.next.next = node52;
  head2.next.next.next.next.next = node62;
  head2.next.next.next.next.next.next = node72;

  System.out.println("linked list-1 [4-->5-->12 -->24 -->83]\n"
    + "linked list-2 [8-->9-->14 --> 21 --> 31 -->132-->136]\n");
  System.out.print("Merged linkedlist using iterative appraoch : ");
  mll.diplayList(mll.mergeSortedLinkedListIterative(head1, head2));

  /* mark head1 = null */
  Node head3 = null;
  System.out.print("\n\nMerged linkedlist iterative appraoch- "
    + "with only List2 has values: ");
  mll.diplayList(mll.mergeSortedLinkedListIterative(head3, head2));

  System.out.print("\n\nMerged linkedlist recursive appraoch- "
    + "with only List1 has values: ");
  mll.diplayList(mll.mergeSortedLinkedListRecursive(head1, head3));

  System.out.print("\n\nMerged linkedlist using recursive appraoch : ");
  mll.diplayList(mll.mergeSortedLinkedListRecursive(head1, head2));

 }
}
===========Sample output===============
linked list-1 [4-->5-->12 -->24 -->83]
linked list-2 [8-->9-->14 --> 21 --> 31 -->132-->136]

Merged linkedlist using iterative appraoch :  [ 4 5 8 9 12 14 21 24 31 83 132 136  ]

Merged linkedlist iterative appraoch- with only List2 has values:  [ 8 9 14 21 31 132 136  ]

Merged linkedlist recursive appraoch- with only List1 has values:  [ 4 5 12 24 83  ]

Merged linkedlist using recursive appraoch :  [ 4 5 8 9 12 14 21 24 31 83 132 136  ]
=======================================
Tags:

1 Comments

Previous Post Next Post