Merge Two Sorted Linked Lists in DSA Python

Mental Model

We combine two sorted lists by always picking the smaller front item from either list until both are empty.

Analogy: Imagine merging two sorted decks of cards by always taking the top card from the deck that has the smaller card on top.

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Dry Run Walkthrough

Input: list1: 1->3->5, list2: 2->4->6

Goal: Create one sorted list containing all elements from both lists

Step 1: Compare heads: 1 (list1) and 2 (list2), pick 1

Merged: 1 -> null
List1: 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Why: 1 is smaller, so it should come first in merged list

Step 2: Compare heads: 3 (list1) and 2 (list2), pick 2

Merged: 1 -> 2 -> null
List1: 3 -> 5 -> null
List2: 4 -> 6 -> null

Why: 2 is smaller, so it comes next

Step 3: Compare heads: 3 (list1) and 4 (list2), pick 3

Merged: 1 -> 2 -> 3 -> null
List1: 5 -> null
List2: 4 -> 6 -> null

Why: 3 is smaller, so it comes next

Step 4: Compare heads: 5 (list1) and 4 (list2), pick 4

Merged: 1 -> 2 -> 3 -> 4 -> null
List1: 5 -> null
List2: 6 -> null

Why: 4 is smaller, so it comes next

Step 5: Compare heads: 5 (list1) and 6 (list2), pick 5

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null
List1: null
List2: 6 -> null

Why: 5 is smaller, so it comes next

Step 6: List1 empty, append remaining List2 nodes

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
List1: null
List2: null

Why: No more nodes in list1, so add all remaining nodes from list2

Result:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA Python

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

def merge_two_sorted_lists(l1, l2):
    dummy = ListNode()  # dummy node to start merged list
    tail = dummy       # tail points to last node in merged list

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1  # attach l1 node
            l1 = l1.next    # move l1 forward
        else:
            tail.next = l2  # attach l2 node
            l2 = l2.next    # move l2 forward
        tail = tail.next    # move tail forward

    tail.next = l1 if l1 else l2  # attach remaining nodes
    return dummy.next

def print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(result) + " -> null")

# Driver code
# Create list1: 1 -> 3 -> 5 -> null
l1 = ListNode(1, ListNode(3, ListNode(5)))
# Create list2: 2 -> 4 -> 6 -> null
l2 = ListNode(2, ListNode(4, ListNode(6)))

merged_head = merge_two_sorted_lists(l1, l2)
print_list(merged_head)

while l1 and l2:

keep comparing heads while both lists have nodes

if l1.val < l2.val:

choose smaller node to add next

tail.next = l1

attach l1 node to merged list

l1 = l1.next

advance l1 pointer

tail.next = l2

attach l2 node to merged list

l2 = l2.next

advance l2 pointer

tail = tail.next

move tail pointer forward to last node

tail.next = l1 if l1 else l2

attach remaining nodes after one list ends

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n + m) because we visit each node in both lists once

Space: O(1) because we only use a few pointers and reuse existing nodes

vs Alternative: Compared to creating a new list and copying values, this approach is more efficient in space and time by reusing nodes directly

Edge Cases

One or both lists empty

Returns the non-empty list or null if both empty

DSA Python

while l1 and l2:

Lists with duplicate values

Duplicates are merged in sorted order without loss

DSA Python

if l1.val < l2.val:

Lists of different lengths

Remaining nodes of longer list appended after shorter ends

DSA Python

tail.next = l1 if l1 else l2

When to Use This Pattern

When you see two sorted lists and need one sorted list, reach for the merge pattern because it efficiently combines them by comparing heads.

Common Mistakes

Mistake: Forgetting to move the tail pointer after attaching a node
Fix: Always advance tail to tail.next after attaching a node

Mistake: Not attaching remaining nodes after one list ends
Fix: Attach leftover nodes with tail.next = l1 if l1 else l2

Summary

It merges two sorted linked lists into one sorted linked list.

Use it when you have two sorted lists and want a single sorted list combining both.

Always pick the smaller front node from either list and attach it to the merged list.