Merged two sorted lists

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

image

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.

 image

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/

Advertisements
This entry was posted in Algorithms, Technical Interview and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s