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.