NUHMAN.com

Introduction

Given a singly linked list, your task is to reorder it as follows:

Given L0 → L1 → … → Ln-1 → Ln,

Reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You must not modify the values in the list nodes, only the node pointers.

Problem Statement

Rearrange a given singly linked list as per the pattern described above in-place.

Example

Input:

1 → 2 → 3 → 4

Output:

1 → 4 → 2 → 3

Input:

1 → 2 → 3 → 4 → 5

Output:

1 → 5 → 2 → 4 → 3

Approach

This is a three-step process:

1️⃣ Find the Middle of the List

Use slow and fast pointers to find the middle node.

2️⃣ Reverse the Second Half

Reverse the list from the middle to the end.

3️⃣ Merge Two Halves

Merge the first half and the reversed second half by alternating nodes.

Go Implementation

go

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Step 1: Find middle
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Step 2: Reverse second half
    prev := (*ListNode)(nil)
    curr := slow.Next
    slow.Next = nil // Split the list into two halves
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }

    // Step 3: 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
    }
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• One pass to find the middle.
• One pass to reverse the second half.
• One pass to merge the lists.

Edge Cases

• Empty list → Do nothing.
• One node → Do nothing.
• Two nodes → Already reordered.

Conclusion

LeetCode 143: Reorder List is a great exercise in linked list manipulation and in-place algorithms. By combining pointer techniques—like the fast/slow pointer and in-place reversal—you can elegantly restructure a list without any extra memory.

This problem is a common interview favorite, especially in tech companies focusing on data structure skills.