# 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)

Complete 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.
__________________________________________________