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:

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)

Complete Code for Both Methods: Run This Code

Output :

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
__________________________________________________
Top Companies Interview Questions..-

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

Like this: Like Loading...