Merge Two Sorted Lists Problem


Description

LeetCode Problem 21. Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
3
4
5
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,5]

Input: l1 = [], l2 = []
Output: []


Solution

The solution to this problem is straightforward. The idea is to compare the nodes from the two lists, and add the smaller node to the new list each time.

First, we set up a head list node to allow us to easily return the head of the merged list later. We also use three pointers currNode, currNode1, and currNode2 to keep track of the current node in the merged list, list 1, and list 2, respectively.

Then we do the following steps until either list 1 or list 2 is empty. If the value of currNode1 is less than or equal to currNode2, we point currNode’s next pointer to currNode1, and point currNode1 to its next node. If the value of currNode2 is less than currNode1, we point currNode’s next pointer to currNode2, and point currNode2 to its next node.

After these steps, at most one of list 1 and list 2 is non-empty. We can point currNode to the non-empty list’s rest elements and return the head node.

The time complexity is O(n+m), where n and m are the length of the lists. The space complexity is O(1).


Sample C++ Code

This is a C++ implementation of the above approach.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;

    ListNode* currNode1 = l1;
    ListNode* currNode2 = l2;
    ListNode* currNode;
    ListNode* head;
    
    currNode1 = l1;
    currNode2 = l2;
    
    if (l1->val <= l2->val) {
        head = l1;
        currNode = l1;
        currNode1 = currNode1->next;
    }
    else {
        head = l2;
        currNode = l2;
        currNode2 = currNode2->next;
    }
    
    while ((currNode1 != NULL) && (currNode2 != NULL)) {
        if (currNode1->val <= currNode2->val) {
            currNode->next = currNode1;
            currNode1 = currNode1->next;
            currNode = currNode->next;
        } else {
            currNode->next = currNode2;
            currNode2 = currNode2->next;
            currNode = currNode->next;
        }
    }
    if (currNode1 == NULL) {
        currNode->next = currNode2;
    } else {
        currNode->next = currNode1;
    }
    
    return head;
    
}

int main() {
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);

    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    ListNode* head = mergeTwoLists(l1, l2);
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}




Related Posts

Intersection Of Two Linked Lists Problem

LeetCode 160. Given the heads of two singly linked-lists headA...

Sort List Problem

LeetCode 148. Given the head of a linked list, return...

Reorder List Problem

LeetCode 143. You are given the head of a singly...

Linked List Cycle Problem

LeetCode 141. Given head, the head of a linked list,...

Linked List Cycle II Problem

LeetCode 142. Given the head of a linked list, return...

Insertion Sort List Problem

LeetCode 147. Given the head of a singly linked list,...