Algorithm Puzzles: Merge Two Sorted Lists

Posted on Edited on In Views: Word count in article: 154 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Merge Two Sorted Lists

Puzzle

Puzzle from leetcode:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Solution

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
class Solution {
 public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (list1 == nullptr) {
      return list2;
    }

    if (list2 == nullptr) {
      return list1;
    }

    ListNode mergedHead = ListNode();
    ListNode* mergedCur = &mergedHead;
    ListNode* list1Cur = list1;
    ListNode* list2Cur = list2;

    while (list1Cur != nullptr || list2Cur != nullptr) {
      if (list1Cur == nullptr) {
        mergedCur->next = new ListNode(list2Cur->val, list2Cur->next);
        break;
      }
      if (list2Cur == nullptr) {
        mergedCur->next = new ListNode(list1Cur->val, list1Cur->next);
        break;
      }

      if (list1Cur->val < list2Cur->val) {
        mergedCur->next = new ListNode(list1Cur->val);
        list1Cur = list1Cur->next;
      } else {
        mergedCur->next = new ListNode(list2Cur->val);
        list2Cur = list2Cur->next;
      }

      mergedCur = mergedCur->next;
    }

    return mergedHead.next;
  }
};

TC: O(2n)