This post is completed by 1 user

  • 0
 Add to List
Medium

Merge or Combine Two Sorted Linked Lists

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example: 




List a : 



->2->6->18





Listb: 



->1->3->17->19





Merged List: ->1->2->3->6->17->18->19



 



Approach:

Without Recursion:






  • Create a new node say result
  • Navigate through both the linked lists at the same time, starting from head
  • Compare the first node values of both the linked lists
  • Whichever is smaller, add it to the result node
  • Move the head pointer of the linked list whose value was smaller
  • Again compare the node values
  • Keep doing until one list gets over
  • Copy the rest of the nodes of unfinished list to the result



With Recursion:



  • Base Case :



If List A gets finished , return List B.


If List B gets finished, return List A.



  • Create a result node and initialize it as NULL
  • Check which node (List A or List B) has a smaller value.
  • Whichever is smaller, add it to the result node.
  • Make recursive call and add the return node as result.next



 result.next = recurrsionMerge(nA.next, nB)




Code:





Method : with Recursion
->5->6->8
->1->3->7->9
->1->3->5->6->7->8->9
Method : without Recursion
->2->6->18
->1->3->17->19
->1->2->3->6->17->18->19















































Also Read: