#143

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Reorder List

Reorder List requires careful pointer manipulation in a singly linked list to interleave nodes from the ends without altering values.

linked list two pointers stack recursion

Problem Statement

You are given the head of a singly linked list. Each node contains an integer value. Your task is to reorder the nodes so that the sequence changes from the original L0 → L1 → L2 → ... → Ln to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... The node values themselves cannot be altered; only the nodes' connections can be modified.

The list may contain up to 50,000 nodes, each with a value between 1 and 1000. You must handle edge cases such as lists with an odd number of nodes or very short lists. Your implementation should be efficient in both time and space while maintaining the linked-list structure intact.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

L0 → L1 → … → Ln - 1 → Ln

Example 2

Input: See original problem statement.

Output: See original problem statement.

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Example 3

Input: head = [1,2,3,4]

Output: [1,4,2,3]

Example details omitted.

Constraints

The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000

Solution Approach

Split the list into halves

Use slow and fast pointers to find the midpoint of the list. Slow moves one step at a time, fast moves two. After traversal, disconnect the first half from the second to prepare for merging.

Reverse the second half

Reverse the second half in place using iterative pointer reversal. This ensures the last nodes are accessible in correct order for interleaving with the first half.

Merge two halves alternatingly

Iteratively merge nodes from the first and reversed second halves. Carefully reassign next pointers to avoid losing nodes, achieving the L0 → Ln → L1 → Ln-1 → ... pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited a constant number of times during split, reverse, and merge. Space complexity is O(1) for in-place reversal and merging, though recursion or a stack can increase space usage if used.

What Interviewers Usually Probe

Check if the candidate can split the list efficiently without extra space.
Watch for correct in-place reversal of the second half.
Ensure merging maintains the alternating pattern without node loss.

Common Pitfalls or Variants

Common pitfalls

Modifying node values instead of pointers, which violates the problem constraints.
Losing reference to the second half while splitting, leading to memory leaks.
Incorrect merging order causing cycles or skipped nodes.

Follow-up variants

Reorder list using recursion instead of iterative merge.
Reorder list using a stack to store the second half for interleaving.
Modify the pattern to L0 → Ln → L1 → Ln-1 → L2 → ... only for odd-length lists.

FAQ

Can I change node values instead of pointers in Reorder List?

No, the problem requires manipulating the actual nodes. Altering values violates constraints and won't be accepted.

What is the easiest way to find the midpoint of a singly linked list?

Use slow and fast pointers: slow moves one node at a time, fast moves two. When fast reaches the end, slow is at midpoint.

Do I need extra space to reorder the list?

An in-place solution requires O(1) extra space, but using a stack or recursion will increase space usage.

How do I merge two halves without losing nodes?

Always store next references before reassigning pointers, and alternate nodes from each half until all nodes are merged.

Is Reorder List considered a Linked-list pointer manipulation pattern?

Yes, the core challenge is rearranging pointers without changing node values, which exemplifies the linked-list pointer manipulation pattern.

terminal

Solution

Solution 1: Fast and Slow Pointers + Reverse List + Merge Lists

We first use fast and slow pointers to find the midpoint of the linked list, then reverse the second half of the list, and finally merge the two halves.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        fast = slow = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        cur = slow.next
        slow.next = None

        pre = None
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        cur = head

        while pre:
            t = pre.next
            pre.next = cur.next
            cur.next = pre
            cur, pre = pre.next, t

Continue Practicing

#234 palindrome linked list #142 linked list cycle ii #141 linked list cycle