This post is completed by 2 users

  • 0
 Add to List
Medium

17. Merge or Combine Two Sorted Linked Lists

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

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 and move the head for that list to the next pointer.
  • 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 any of the list is finished, return the other list.
  • Create a result node and initialize it as NULL
  • Compare the first node values of both the linked lists
  • Whichever is smaller, add it to the result node and move the head for that list to the next pointer.
  • Make recursive call with the heads of both the lists. 
  • Add the returned node from the recursive call to the result.next
  • Example - result.next = recursionMerge(nA.next, nB)
  • Look at the code below for more understanding.

->2->6->18
->1->3->9->17
->1->2->3->6->9->17->18

Related Problems: