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.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To create a new sorted linked list containing all elements from both lists

B. To reverse the order of elements in both lists

C. To find the largest element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging two sorted linked lists means combining them into one list that keeps the sorted order.

2. Step 2: Identify the goal

   The goal is to have a new linked list that contains all elements from both lists in sorted order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option A

4. Quick Check:

   Merging = combine sorted lists [OK]

Hint: Merging keeps order and combines all elements [OK]

Common Mistakes:

• Thinking merging reverses lists
• Only finding largest element
• Removing duplicates instead of merging

2. Which of the following is the correct way to start merging two sorted linked lists in Python?

easy

A. def mergeLists(l1, l2):
current = ListNode(0)
dummy = current.next

B. def mergeLists(l1, l2):
dummy = null
current = dummy

C. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy

D. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy.next

Solution

1. Step 1: Initialize dummy and current nodes properly

   We create a dummy node with value 0 and set current to dummy to build the merged list.

2. Step 2: Check options for correct syntax

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy correctly creates dummy and current pointing to dummy. def mergeLists(l1, l2): dummy = ListNode(0) current = dummy.next incorrectly sets current = dummy.next which is initially None.

3. Final Answer:

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy -> Option C

4. Quick Check:

   Dummy node with value 0 starts merge [OK]

Hint: Start with dummy node value 0 and current pointing to dummy [OK]

Common Mistakes:

• Setting current to dummy.next
• Swapping dummy and current incorrectly
• Setting dummy to null

3. What will be the output linked list after merging these two sorted lists? List 1: 1 -> 3 -> 5 -> null List 2: 2 -> 4 -> 6 -> null Use the merge logic to combine them.

medium

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

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

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

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

Solution

1. Step 1: Compare nodes from both lists in order

   Start with 1 (List 1) and 2 (List 2). 1 is smaller, add 1. Then compare 3 and 2, add 2. Continue comparing and adding smaller nodes.

2. Step 2: Build merged list step-by-step

   Merged list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null after adding all nodes in sorted order.

3. Final Answer:

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

4. Quick Check:

   Sorted merge combines nodes in ascending order [OK]

Hint: Pick smaller node each step to keep order [OK]

Common Mistakes:

• Appending one list fully before the other
• Mixing node order incorrectly
• Skipping nodes during merge

4. Identify the error in this merge function snippet:

def mergeLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
    current.next = l1 if l1 else l2
    return dummy.next

medium

A. The 'current' pointer is not moved forward inside the loop

B. The dummy node is not initialized correctly

C. The function does not handle empty input lists

D. The return statement should return 'current' instead of 'dummy.next'

Solution

1. Step 1: Check pointer updates inside the loop

   After assigning current.next, the current pointer must move forward to current.next to continue building the list.

2. Step 2: Identify missing current update

   The code misses 'current = current.next' inside the while loop, causing an infinite loop or incorrect list.

3. Final Answer:

   The 'current' pointer is not moved forward inside the loop -> Option A

4. Quick Check:

   Move current forward after linking nodes [OK]

Hint: Always move current pointer after linking a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Returning wrong node
• Not handling empty lists (though not error here)

5. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what should the merged list be?

medium

A. 0 -> null

B. null

C. 4 -> 2 -> 0 -> null

D. 0 -> 2 -> 4 -> null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the non-empty list as it is already sorted.

2. Step 2: Apply to given lists

   Since the second list is empty and the first is 0 -> 2 -> 4 -> null, the merged list remains 0 -> 2 -> 4 -> null.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option D

4. Quick Check:

   Merging with empty list returns the other list [OK]

Hint: Empty list merge returns the other list unchanged [OK]

Common Mistakes:

• Returning null when one list is empty
• Reversing the non-empty list
• Returning only the first node