This post is completed by 1 user
|
Add to List |
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)
Code:
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
Also Read: