DSA sheet · Linked List · Merge / Sort pattern

Merge Two Sorted Lists

This video opens a new pattern in the linked list sheet: the merge / sort pattern. The teacher has finished the first three patterns and now brings in the logic of the merge step of merge sort. Merge Two Sorted Lists is the first problem of this pattern and the building block for the later ones (Sort List, Merge K Sorted Lists). She first shows a brute force (copy into an array, sort, rebuild), explains why it is not good enough for an interview, and then shows the real answer: stitch the existing nodes together with a dummy node and a moving tail pointer.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists from scratch (and the tools this page uses)
• Part A · Brute force: array + sort + rebuild
• Part B · Optimal: merge with a dummy node and a tail pointer
• Part C · Revision page

Part 0 · Before starting

What is a node?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a link to the next node (next). The last node's next is None, which means "the chain ends here".

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end

  [1] → [2] → [4] → None
   ↑
  head

The head is the first node. If you have the head, you can reach every node. If the list is empty, the head itself is None.

Walking a list

To visit every node, keep a pointer curr and move it one step at a time with curr = curr.next, until it becomes None.

curr = head
while curr is not None:
    print(curr.val)
    curr = curr.next      # one step forward

No index access

An array lets you jump to a[5] in one step, because the elements sit next to each other in memory. A linked list's nodes can be anywhere in memory; the only way to reach node number i is to start at the head and walk i steps. So reaching position i costs O(n), not O(1). That's why linked list solutions are written with pointers that walk, not with indexes.

Save next before you change a pointer

A node only knows its next node through node.next. If you overwrite node.next and haven't saved the old value somewhere, the rest of the chain is lost. In this problem we're safe because the two list heads (list1, list2) always keep hold of the unattached part, as you'll see.

Tool 1: the dummy node

A dummy node is a fake node (value 0, say) that we create just to stand in front of the answer list. Why? When we build a new chain, the very first node is special: there's nothing before it to attach it to, so we'd need an extra if head is None: case. With a dummy at the front, every real node, including the first, is attached the same way: tail.next = node. At the end the real answer starts at dummy.next.

  dummy
  [0] → [1] → [1] → [2] → ...
         ↑
   real answer starts here (dummy.next)

Tool 2: merging with a tail pointer

The tail pointer (the teacher calls it current) always sits on the last node of the answer built so far. To add a node: current.next = node, then move current = current.next. Everything from dummy up to current is finished and sorted.

The merge idea (from merge sort)

Merge sort's merge step takes two already sorted sequences and joins them into one sorted sequence by repeatedly picking the smaller front element. The teacher says this algorithm is the prerequisite for the video. On arrays you use indexes i and j; here we use the two list pointers instead, and we move nodes, not values.

Part A · Brute force: array + sort + rebuild

LeetCode 21

1The question in simple words

You get the heads of two linked lists, list1 and list2. Each one is already sorted (small to large). Join them into one sorted linked list and return its head. LeetCode also says the new list should be made by splicing together the nodes of the two lists.

  list1:  [1] → [2] → [4] → None
  list2:  [1] → [3] → [4] → None

  answer: [1] → [1] → [2] → [3] → [4] → [4] → None

2What the constraints tell us

• Each list has 0 to 50 nodes. That's tiny. Anything works, even sorting. So the teacher says: suppose you don't know the merge algorithm, you could still pass with a brute force.
• 0 nodes is allowed, so either list (or both) can be None. The code must survive that.
• Both lists are sorted in non-decreasing order. Keep this in mind; it's the clue for Part B.

3Intuition

Forget that the inputs are linked lists. Pour all the numbers into one ordinary Python list, let Python sort them, and then build a brand-new linked list from the sorted numbers.

4Building the logic

1. Walk list1 and copy each value into an array: [1, 2, 4].
2. Walk list2 and append its values: [1, 2, 4, 1, 3, 4].
3. Sort with the built-in sort: [1, 1, 2, 3, 4, 4].
4. Create new nodes 1 → 1 → 2 → 3 → 4 → 4 and return the head.

This gets accepted, because n is at most 50.

5Approach steps

1. Collect all values of both lists in an array.
2. Sort the array.
3. Build a new linked list from it (a dummy node makes this easy) and return dummy.next.

6Code (Python)

class Solution:
    def mergeTwoLists(self, list1, list2):
        values = []
        curr = list1
        while curr:                    # read list1
            values.append(curr.val)
            curr = curr.next
        curr = list2
        while curr:                    # read list2
            values.append(curr.val)
            curr = curr.next

        values.sort()                  # built-in sort

        dummy = ListNode(0)            # build a NEW list
        tail = dummy
        for v in values:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

7Code line by line

8Dry run

9Complexity & remember

• Time: O(n + m) to read both lists, then O((n + m) log(n + m)) for the sort. The sort dominates.
• Space: O(n + m) for the array, plus another O(n + m) for the brand-new nodes.

Part B · Optimal: merge with a dummy node and a tail pointer

1The question in simple words

Same question. Now we want to use the fact that both lists are sorted, so we don't sort again, and we want to reuse the existing nodes instead of creating new ones.

2What the constraints tell us

• Both lists are sorted → we can use merge, which is linear: O(n + m). We drop the log factor.
• A list can be empty → our loop must not read .val of None; and if one list is empty from the start, the answer is just the other list.

3Intuition: two queues of people sorted by height

Picture two lines of people, each line already sorted from shortest to tallest. You want one sorted line. You don't need to re-sort anybody: just look at the front person of each line, send the shorter one to the new line, and repeat. When one line runs out, the other line is already sorted, so the whole rest of it walks over at once.

In the list version, the "front person" is the node at list1 or list2, and "send to the new line" means current.next = that node.

4Building the logic step by step

The teacher works with list1 = 1 → 2 → 4 and list2 = 1 → 3 → 4.

  dummy                 list1: [1] → [2] → [4] → None
  [0]                   list2: [1] → [3] → [4] → None
   ↑
 current

Step 1: pick the smaller front, ties go to list1

Compare list1.val (1) and list2.val (1). They're equal; the teacher decides that on a tie we take list1. So the check is list1.val <= list2.val.

We attach it: current.next = list1. Notice that this hooks up the whole remaining list1 (1 → 2 → 4), not just one node, because list1's first node still points to the rest. That's fine: the parts that shouldn't stay there will be cut off later when we rewire.

  [0] → [1] → [2] → [4] → None        list2: [1] → [3] → [4] → None
   ↑     ↑
 current list1

Step 2: move list1 forward. Why?

list1 = list1.next. The teacher gives two reasons:

1. That first 1 is already placed in the answer. If list1 stayed on it, next time we might attach the same chain (1 → 2 → 4) again.
2. The next candidate from list1 is now 2; that's the node that must be compared with list2's front next time, not the old 1.

Step 3: otherwise, take from list2

If list2's front is smaller: current.next = list2, then list2 = list2.next, for the same two reasons.

Step 4: always move current

Whichever branch ran, one more node is now in place, so current = current.next. Current again sits on the last finished node. "Everything from dummy up to current is sorted."

  after step 1 + moves:
  [0] → [1] → [2] → [4] → None        list2: [1] → [3] → [4] → None
         ↑     ↑                               ↑
     current  list1                          list2

Next round: 2 vs 1 → list2's 1 is smaller → current.next = list2. The link from the first 1 to 2 is overwritten; now the first 1 points to list2's 1 (which still leads to 3 → 4). Did we lose 2 → 4? No: list1 is still holding it. This is the "save next first" rule in action: the list heads are our saved pointers.

  [0] → [1] → [1] → [3] → [4] → None     list1: [2] → [4] → None
               ↑     ↑                          ↑
           current  list2                     list1

Step 5: when do we stop? Both must be non-None

Keep going while both lists still have nodes. If one is None and we still try list1.val, we'd be reading the value of nothing (Java gives a null pointer exception; Python gives AttributeError). So the loop is while list1 and list2.

Step 6: one list runs out, attach the other as it is

In the example, list1 runs out first while list2 still holds the last 4. The teacher asks: what if list2 had been 4 → 5 → 6 at this point? Do we need to keep comparing? No. list2 was sorted on its own, so its leftover part is sorted, and every value in it is ≥ everything already placed. Just hook it on: current.next = list2. The opposite can also happen (list2 ends first, list1 still has, say, 5 → 6), so we write both checks:

if list1 is not None:
    current.next = list1
if list2 is not None:
    current.next = list2

Step 7: return dummy.next

dummy is our fake 0 node. The real head is the node after it: return dummy.next.

5Approach steps

1. Make dummy = ListNode(0) and current = dummy.
2. While both list1 and list2 are not None:
   • if list1.val <= list2.val: attach list1, move list1;
   • else: attach list2, move list2;
   • move current.
3. Attach whichever list is still left (no comparing needed).
4. Return dummy.next.

6Code (Python)

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        current = dummy

        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                current.next = list1      # take list1's front
                list1 = list1.next
            else:
                current.next = list2      # take list2's front
                list2 = list2.next
            current = current.next        # one more node is in place

        if list1 is not None:             # leftovers are already sorted
            current.next = list1
        if list2 is not None:
            current.next = list2

        return dummy.next

Shorter way, same meaning: the two final ifs can be written as current.next = list1 if list1 else list2.

7Code line by line

8Dry run: list1 = 1 → 2 → 4, list2 = 1 → 3 → 4

To tell equal values apart: a = list1's nodes (1a, 2a, 4a), b = list2's nodes (1b, 3b, 4b).

Snapshot after step 2 (the 1a → 2a link is gone, but list1 still holds 2a):

  [0] → [1a] → [1b] → [3b] → [4b] → None
                 ↑      ↑
              current  list2

  list1 → [2a] → [4a] → None     (not lost: list1 points to it)

Snapshot after step 4:

  [0] → [1a] → [1b] → [2a] → [3b] → [4b] → None
                               ↑      ↑
                            current  list2
  list1 → [4a] → None

Final:

  [0] → [1a] → [1b] → [2a] → [3b] → [4a] → [4b] → None
  dummy  ↑
        returned head

9Complexity & remember

• Time O(n + m): each loop round places exactly one node, and the leftover is attached in one step. No sorting, so no log factor. On LeetCode this ran faster than the brute force for exactly this reason.
• Space O(1): just the dummy node and a few pointers. We reused the original nodes.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.mergeTwoLists(build([1, 2, 4]), build([1, 3, 4]))))  # [1, 1, 2, 3, 4, 4]
print(to_list(s.mergeTwoLists(build([]), build([]))))                # []
print(to_list(s.mergeTwoLists(build([]), build([0]))))               # [0]
print(to_list(s.mergeTwoLists(build([5, 6]), build([1, 2, 3]))))     # [1, 2, 3, 5, 6]

Based on this video: Merge Two Sorted Lists