Home
How to Merge Two Sorted Lists (Recursion and Iterative)?
Tags:, , ,

How to Merge Two Sorted Lists (Recursion and Iterative)?

April 8, 2016 No Comments algorithms, c / c++, coding exercise, data structure, recursive

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.

Merging two sorted linked list is intuitive: every time choosing the node with a smaller value from two lists and move forward that chosen list, until we reach the end of a list. Then we just have to append the remainding list to the target.

Recursion

Code written in Recursion can be very straightforward. This is no exception. We are required to re-use the current linked lists without allocating a new list. The idea is to choose the smaller value of both lists. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Recursion merge two lists from the top to the bottom. When one of the list is empty, the terminal condition is to return the other list.

Iterative

The same algorithm can be implemented using a iterative approach – which avoids possible stack-over-flow and could be somehow more efficient. Most recursion (except e.g. Ackermann function) can be re-written using a iterative loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode* node = &head;
    
        while(l1 && l2) {
            ListNode*& next = (l1->val < l2->val)  ? l1 : l2;
            node->next = next;
            node = next;
            next = next->next;
        }    
        node->next = l1 ? l1 : l2;
        return head.next;
    }
};
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode* node = &head;
    
        while(l1 && l2) {
            ListNode*& next = (l1->val < l2->val)  ? l1 : l2;
            node->next = next;
            node = next;
            next = next->next;
        }    
        node->next = l1 ? l1 : l2;
        return head.next;
    }
};

The next node is a reference ListNode* type so the following:

1

next = next->next;
next = next->next;

is actually equivalent to:

1
2
3
4
5

if (l1->val < l2->val) {
    l1 = l1->next;
} else {
    l2 = l2->next;
}
if (l1->val < l2->val) {
    l1 = l1->next;
} else {
    l2 = l2->next;
}

Here is my implementation on one of the Mock facebook interview:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        dummy->next = l1->val <= l2->val ? l1 : l2;        
        ListNode *p = dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }                        
        }
        if (l1 != nullptr) p->next = l1;
        if (l2 != nullptr) p->next = l2;
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        dummy->next = l1->val <= l2->val ? l1 : l2;        
        ListNode *p = dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }                        
        }
        if (l1 != nullptr) p->next = l1;
        if (l2 != nullptr) p->next = l2;
        return dummy->next;
    }
};

Here is an alternative using for loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode result(-1);
        for (ListNode* it = &result; l1 != NULL || l2 != NULL; it = it->next) {
            int val1 = l1 == NULL ? INT_MAX : l1->val;
            int val2 = l2 == NULL ? INT_MAX : l2->val;
            auto n = (val1 <= val2) ? l1 : l2; 
            it->next = n;
            if (val1 <= val2) {
                l1 = l1->next;
            }
            else {
                l2 = l2->next;
            }
        }
        return result.next;
    }
};
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode result(-1);
        for (ListNode* it = &result; l1 != NULL || l2 != NULL; it = it->next) {
            int val1 = l1 == NULL ? INT_MAX : l1->val;
            int val2 = l2 == NULL ? INT_MAX : l2->val;
            auto n = (val1 <= val2) ? l1 : l2; 
            it->next = n;
            if (val1 <= val2) {
                l1 = l1->next;
            }
            else {
                l2 = l2->next;
            }
        }
        return result.next;
    }
};

A nice trick here is to use a dummy head Linked Node and return its next.

See also: Merge Two Sorted Linked List using GoLang

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
696 words
Last Post: C++ Coding Exercise - Product of Array Except Self
Next Post: How to Check for Duplication in C++?

The Permanent URL is: How to Merge Two Sorted Lists (Recursion and Iterative)?

Related posts:

  1. The String ZigZag Conversion Algorithms The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows...
  2. The Custom Sort String Algorithm with Count and Write S and T are strings composed of lowercase letters. In S, no letter occurs more...
  3. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  4. Get Help With SQL Database Design and Development For Your Business with SQL Server Consulting If you want to design an SQL database from scratch, revamp an existing system, or...
  5. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  6. Breadth First Search Algorithm to Find Nearest Right Node in Binary Tree Given the root of a binary tree and a node u in the tree, return...
  7. How to Fix eslint linebreak style error on Visual Studio Code Windows? (Expected linebreaks to be ‘crlf’ but found ‘lf’) Suddenly, you run npm run lint and it shows quite a lot of linebreak-style errors....
  8. Binary Tree Algorithm: Checking Leaves in the Same Level Given a binary tree root, return whether all leaves are at the same level. Constraints...

Leave a Reply