Reorder Linked List in DSA Go - 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 reordering it with the given function?

DSA Go

package main
import "fmt"
type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    // Find middle
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // Reverse second half
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }
    // Merge two halves
    first, second := head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println(" -> null")
}

func main() {
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}
    reorderList(head)
    printList(head)
}

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

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

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

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

💡 Hint

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

The reorderList function splits the list into two halves, reverses the second half, and then merges nodes alternately from the first and reversed second half. This results in the pattern: first node, last node, second node, second last node, and so on.

❓ Predict Output

intermediate

Resulting List After Reorder on Even Length List

Given the linked list 10 -> 20 -> 30 -> 40, what is the printed state after applying the reorderList function?

DSA Go

package main
import "fmt"
type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }
    first, second := head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println(" -> null")
}

func main() {
    head := &ListNode{10, &ListNode{20, &ListNode{30, &ListNode{40, nil}}}}
    reorderList(head)
    printList(head)
}

A 10 -> 20 -> 30 -> 40 -> null

B 10 -> 40 -> 20 -> 30 -> null

C 40 -> 30 -> 20 -> 10 -> null

D 10 -> 30 -> 40 -> 20 -> null

💡 Hint

Remember the second half is reversed before merging.

The list is split into two halves: 10 -> 20 and 30 -> 40. The second half is reversed to 40 -> 30. Then merged alternately: 10 -> 40 -> 20 -> 30.

🔧 Debug

advanced

Identify the Error in Reorder Function

What error will this code produce when run?

DSA Go

package main
import "fmt"
type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }
    first, second := head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

func main() {
    var head *ListNode = nil
    reorderList(head)
    fmt.Println("Done")
}

A Compilation error: undefined variable 'head'

B Runtime panic: invalid memory address or nil pointer dereference

C No output, program runs successfully printing 'Done'

D Infinite loop causing program to hang

💡 Hint

Check how the function handles empty list input.

The function checks if head is nil or head.Next is nil and returns immediately, so no panic occurs. The program prints 'Done' successfully.

❓ Predict Output

advanced

Output After Reordering Single Node List

What is the output of the following code?

DSA Go

package main
import "fmt"
type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }
    first, second := head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println(" -> null")
}

func main() {
    head := &ListNode{42, nil}
    reorderList(head)
    printList(head)
}

A 42 -> null

B null

C 42 -> 42 -> null

D Runtime panic: nil pointer dereference

💡 Hint

A single node list should remain unchanged after reorder.

The function returns immediately if the list has zero or one node, so the list remains unchanged and prints '42 -> null'.

🚀 Application

expert

Order of Operations in Reorder List Function

Which option correctly represents the order of key steps in the reorderList function?

A 1,3,2,4

B 1,2,3,4

C 3,1,2,4

D 2,1,3,4

💡 Hint

Think about when the list is split and when the second half is reversed.

First, the middle is found (1). Then the list is split by setting middle's next to nil (3). Next, the second half is reversed (2). Finally, the two halves are merged (4).

Practice

1. What is the main goal of the Reorder Linked List problem?

easy

A. Rearrange the list so nodes alternate from start and end towards the center

B. Sort the linked list in ascending order

C. Reverse the entire linked list

D. Remove duplicate nodes from the linked list

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the list so that nodes come alternately from the start and the end, like L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 and so on.

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the entire list, but a specific pattern of rearrangement.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end towards the center -> Option A

4. Quick Check:

   Reorder = alternate start/end nodes [OK]

Hint: Think of weaving nodes from front and back alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Trying to reverse the whole list only
• Ignoring the alternating pattern

2. Which of the following Go code snippets correctly declares a singly linked list node struct for the reorder linked list problem?

easy

A. class ListNode { int val; ListNode next; }

B. type ListNode struct { Val int; Next *ListNode }

C. struct ListNode { int Val; ListNode* Next; }

D. type ListNode struct { Value int; NextNode *ListNode }

Solution

1. Step 1: Identify Go struct syntax

   In Go, structs are declared with the keyword type, fields have names and types separated by spaces, and pointers use *.

2. Step 2: Match correct field names and types

   type ListNode struct { Val int; Next *ListNode } uses Val int and Next *ListNode, which is the standard for singly linked list nodes in Go.

3. Final Answer:

   type ListNode struct { Val int; Next *ListNode } -> Option B

4. Quick Check:

   Go struct with pointer field = type ListNode struct { Val int; Next *ListNode } [OK]

Hint: Remember Go struct fields: name type; pointer uses * [OK]

Common Mistakes:

• Using C/C++ or Java syntax in Go
• Missing pointer * for next node
• Incorrect field names or types

3. Given the linked list 1 -> 2 -> 3 -> 4 -> 5 -> null, what is the reordered list after applying the reorder linked list algorithm?

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern

   The reorder pattern takes the first node, then the last node, then second node, then second last node, and so on.

2. Step 2: Apply pattern to given list

   Start: 1, end: 5, then 2, then 4, then 3 in the middle. So the reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> null.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes = 1 -> 5 -> 2 -> 4 -> 3 -> null [OK]

Hint: Pick nodes alternately from front and back [OK]

Common Mistakes:

• Reversing the entire list instead
• Keeping original order unchanged
• Mixing node order incorrectly

4. Consider this Go function snippet for reordering a linked list:

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil { return }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    second := slow.Next
    slow.Next = nil
    var prev *ListNode
    for second != nil {
        next := second.Next
        second.Next = prev
        prev = second
        second = next
    }
    first, second = head, prev
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

What is the bug in this code?

medium

A. The function does not handle empty or single-node lists

B. The middle node is not correctly found; slow pointer should start at head.Next

C. The loop to reverse the second half does not update the prev pointer correctly

D. The reversed second half is not properly linked back to the first half

Solution

1. Step 1: Analyze the reversal and merging steps

   The code correctly finds the middle, reverses the second half, and then merges nodes alternately.

2. Step 2: Identify the bug in linking halves

   After merging, the last node of the reordered list may still point to old nodes if not handled carefully. The code misses ensuring the last node's Next is nil, causing potential cycle or dangling links.

3. Final Answer:

   The reversed second half is not properly linked back to the first half -> Option D

4. Quick Check:

   Linking halves correctly is key [OK]

Hint: Check if last node's Next is set to nil after merge [OK]

Common Mistakes:

• Not breaking the list at middle properly
• Forgetting to set slow.Next = nil
• Incorrect pointer updates in merge loop

5. You have a linked list with nodes containing values 1 -> 2 -> 3 -> null. After reordering, what will be the list if you apply the reorder linked list algorithm twice in a row?

hard

A. 1 -> 3 -> 2 -> null (same as after first reorder)

B. 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> null (original list)

D. 2 -> 3 -> 1 -> null

Solution

1. Step 1: Apply reorder once

   First reorder transforms 1->2->3 into 1->3->2.

2. Step 2: Apply reorder again on the new list

   Reordering 1->3->2 again returns the original order 1->2->3 because the reorder pattern is symmetric and reverses itself on second application.

3. Final Answer:

   1 -> 2 -> 3 -> null (original list) -> Option C

4. Quick Check:

   Reorder twice returns original list [OK]

Hint: Reordering twice restores original order [OK]

Common Mistakes:

• Assuming reorder twice keeps the first reorder result
• Not recognizing reorder symmetry
• Confusing reorder with reverse