Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Merge or Combine Two Sorted Linked Lists

Objec­tive: Given two sorted linked lists, objec­tive 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:

With­out Recursion:

  • Cre­ate a new node say result
  • Nav­i­gate through both the linked lists at the same time, start­ing from head
  • Com­pare the first node val­ues 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 com­pare the node values
  • Keep doing until one list gets over
  • Copy the rest of the nodes of unfin­ished list to the result

With Recur­sion:

  • Base Case :

If List A gets fin­ished , return List B.

If List B gets fin­ished, return List A.

  • Cre­ate a result node and ini­tial­ize 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 recur­sive call and add the return node as result.next

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

Com­plete Code:


Out­put:

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

You may also like...