Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists
There may be one more ways to solve this problem. We define the function which return the merged list as:
struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B)
The simple solution is using recursion. When we compare two nodes from A and B, we need to put the node having smaller value into the merged list. So we select node with data 2 in A here, because 2 < 3. The next selected node will be linked to A->next. The code which implements the idea using recursion would look like:
if ( A->val < B->val ) A->next = mergeTwoLists( A->next, B )
It’s always important to make sure to check NULL condition. When either of linked list reaches to its end (NULL), we just put the rest of the nodes in the other linked list to merged list.
The other way is not using recursion and it’s a bit complicating. In recursive solution, we don’t need to allocate memory to store the current state in stack. When recursively calling the next mergeTwoLists, the current states are implicitly saved in the stack. The stack stores pointer of head and current node. With non-reclusive solution we need to explicitly allocates at least two more variables, head and cur to save head and current node pointer respectively.
We first determine the head by comparing heads in A and B. Because 2 < 3, head of A is selected for head of merged list. Then update A with A->next. To trace tail of the merged list, we use cur. At the next step, compare A (now A has 5) and B (3). Because 3 < 5, the node B with data 3 is assigned to cur->next. We update cur = cur->next and B = B->next and continue to loop with the next node pair.
-Question from: https://leetcode.com/problems/merge-two-sorted-lists/