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: