How to merge 2 Sorted Linked list in C++?

Example:

L1: 1 →4 →6 →8 →10

L2: 5→7 →9 →11 →12

Result: 1 →4 →5 →6 →7 →9 →10 →11 →12

Pseudo Code:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Recursive Method:

1. Compare the head of both lists.
2. Find the smaller node among the two head nodes. The current element will be the smaller node among two head nodes.
3. The rest elements of both lists will appear after that.
4. Now run a recursive function with parameters, the next node of the smaller element and the other head.
5. The recursive function will return the next smaller element linked with rest of the sorted element. Now point the next of current element to that, i.e curr_ele->next=recursivefunction()
6. Handle some corner cases.

• If both the heads are NULL return null.
• If one head is null return the other.