Merge Two Sorted Linked Lists in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after merging two sorted linked lists?

Given two sorted linked lists:

List 1: 1 -> 3 -> 5 -> null

List 2: 2 -> 4 -> 6 -> null

What is the merged linked list?

DSA Python

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

def merge_lists(l1, l2):
    dummy = Node(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 = current.next
    current.next = l1 or l2
    return dummy.next

# Construct lists
l1 = Node(1)
l1.next = Node(3)
l1.next.next = Node(5)
l2 = Node(2)
l2.next = Node(4)
l2.next.next = Node(6)

merged = merge_lists(l1, l2)
result = []
while merged:
    result.append(merged.val)
    merged = merged.next
print(result)

A [1, 2, 4, 3, 5, 6]

B [1, 2, 3, 4, 5, 6]

C [1, 3, 5, 2, 4, 6]

D [2, 4, 6, 1, 3, 5]

💡 Hint

Compare the head nodes of both lists and attach the smaller one to the merged list.

The function merges two sorted linked lists by always choosing the smaller current node from either list. The final merged list is sorted.

❓ Predict Output

intermediate

What is the output of merging when one list is empty?

Given two linked lists:

List 1: null (empty)

List 2: 0 -> 7 -> 8 -> null

What is the merged linked list?

DSA Python

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

def merge_lists(l1, l2):
    dummy = Node(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 = current.next
    current.next = l1 or l2
    return dummy.next

# Construct lists
l1 = None
l2 = Node(0)
l2.next = Node(7)
l2.next.next = Node(8)

merged = merge_lists(l1, l2)
result = []
while merged:
    result.append(merged.val)
    merged = merged.next
print(result)

A [0]

B []

C [7, 8]

D [0, 7, 8]

💡 Hint

If one list is empty, the merged list is just the other list.

The function returns the non-empty list when the other is empty, so the merged list is [0, 7, 8].

🔧 Debug

advanced

What error does this code raise when merging two sorted linked lists?

Consider the following code snippet:

def merge_lists(l1, l2):
    dummy = Node(0)
    current = dummy
    while l1 or l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    return dummy.next

What error will this code raise if either l1 or l2 is None?

A AttributeError: 'NoneType' object has no attribute 'val'

B TypeError: unsupported operand type(s) for <

C SyntaxError: invalid syntax

D IndexError: list index out of range

💡 Hint

Check what happens when you try to access val on a None object.

The condition while l1 or l2 allows l1 or l2 to be None inside the loop. Accessing l1.val or l2.val when they are None causes an AttributeError.

❓ Predict Output

advanced

What is the merged list output for overlapping values?

Given two sorted linked lists:

List 1: 1 -> 3 -> 5 -> 7 -> null

List 2: 3 -> 4 -> 7 -> 8 -> null

What is the merged linked list?

DSA Python

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

def merge_lists(l1, l2):
    dummy = Node(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 = current.next
    current.next = l1 or l2
    return dummy.next

# Construct lists
l1 = Node(1)
l1.next = Node(3)
l1.next.next = Node(5)
l1.next.next.next = Node(7)
l2 = Node(3)
l2.next = Node(4)
l2.next.next = Node(7)
l2.next.next.next = Node(8)

merged = merge_lists(l1, l2)
result = []
while merged:
    result.append(merged.val)
    merged = merged.next
print(result)

A [1, 3, 3, 4, 5, 7, 7, 8]

B [1, 3, 4, 5, 7, 8]

C [1, 3, 5, 7, 3, 4, 7, 8]

D [3, 3, 4, 5, 7, 7, 8, 1]

💡 Hint

Duplicates are kept and merged in sorted order.

The merge keeps all nodes including duplicates, sorted by value.

🚀 Application

expert

How many nodes are in the merged list after merging these two sorted linked lists?

List 1 has nodes with values: 2, 4, 6, 8, 10

List 2 has nodes with values: 1, 3, 5, 7, 9, 11

After merging, how many nodes does the merged linked list contain?

A 9

B 10

C 11

D 12

💡 Hint

The merged list contains all nodes from both lists combined.

List 1 has 5 nodes, List 2 has 6 nodes, so merged list has 5 + 6 = 11 nodes.

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