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.


List a : ->2->6->18

Listb: ->1->3->17->19

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


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 = recurrsionMerge(, nB)

Complete Code for Both Methods:


Method : with Recursion
Method : without Recursion

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: