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
```