Reorder Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Reordering a Linked List

What is the printed state of the linked list after running the reorder function on the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

DSA Python

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

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

def reorder_list(head):
    if not head or not head.next:
        return
    # Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
reorder_list(head)
print_list(head)

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

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

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

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

💡 Hint

Think about splitting the list, reversing the second half, then merging.

The reorder_list function splits the list into two halves, reverses the second half, then merges nodes alternately from the first and reversed second half. This results in the order 1 -> 5 -> 2 -> 4 -> 3 -> null.

🧠 Conceptual

intermediate

Understanding the Purpose of Reordering

What is the main goal of the 'Reorder Linked List' algorithm?

A To rearrange the list so that nodes alternate from the start and end towards the center.

B To sort the linked list in ascending order.

C To remove duplicate nodes from the linked list.

D To reverse the entire linked list.

💡 Hint

Think about how the first and last nodes are placed after reordering.

The reorder algorithm rearranges nodes so the first node is followed by the last node, then the second node, then the second last, and so on, alternating from start and end.

🔧 Debug

advanced

Identify the Error in Reordering Code

What error will this code produce when trying to reorder the list 1 -> 2 -> 3 -> 4 -> null? class Node: def __init__(self, val=0, next=None): self.val = val self.next = next def reorder_list(head): slow, fast = head, head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next prev, curr = None, slow.next slow.next = None while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt first, second = head, prev while second: tmp1 = first.next tmp2 = second.next first.next = second second.next = tmp1 first = tmp1 second = tmp2 head = Node(1, Node(2, Node(3, Node(4)))) reorder_list(head)

A AttributeError because 'NoneType' object has no attribute 'next'

B No error, code runs correctly

C TypeError due to wrong variable assignment

D Infinite loop causing program to hang

💡 Hint

Check the while loop condition for finding the middle.

The condition 'while fast.next and fast.next.next' can cause fast to be None in some cases, leading to AttributeError when accessing fast.next.next.

📝 Syntax

advanced

Correct the Syntax Error in Reorder Function

Which option fixes the syntax error in this code snippet? reorder_list = lambda head: ( slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next )

A Add parentheses around the while loop inside lambda

B Remove the while loop and use a for loop instead

C Replace lambda with def and add colon after function name

D Add a return statement inside the lambda

💡 Hint

Lambda functions cannot contain statements like loops.

Lambda functions in Python can only contain expressions, not statements like loops. Changing to a def function with proper syntax fixes the error.

🚀 Application

expert

Number of Nodes After Reordering

Given a linked list with 7 nodes, after applying the reorder list algorithm, how many nodes will be in the final list?

A 5 nodes

B 6 nodes

C 8 nodes

D 7 nodes

💡 Hint

Reordering changes order but not the number of nodes.

The reorder algorithm rearranges nodes but does not add or remove any nodes, so the count remains the same.