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

Difficulty: Easy

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.

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B) { if ( A == NULL ) return B; if ( B == NULL ) return A; if ( A->val < B->val ) { A->next = mergeTwoLists( A->next, B ); return A; } else { B->next = mergeTwoLists( A, B->next ); return B; } }

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.

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B) { struct ListNode* head = NULL, * cur; if ( A == NULL ) return B; if ( B == NULL ) return A; while ( A != NULL && B != NULL ) { if ( A->val < B->val ) { if ( head == NULL ) { cur = head = A; A = A->next; continue; } cur->next = A; A = A->next; } else { if ( head == NULL ) { cur = head = B; B = B->next; continue; } cur->next = B; B = B->next; } cur = cur->next; } if ( A != NULL ) cur->next = A; if ( B != NULL ) cur->next = B; return head; }

*-Question from: **https://leetcode.com/problems/merge-two-sorted-lists/*