Back to Problems

Reorder List

Medium
Fast & Slow Pointers

You are given the head of a singly linked-list. The list can be represented as:

L0 -> L1 -> ... -> Ln - 1 -> Ln

Reorder the list to be in the following form:

L0 -> Ln -> L1 -> Ln - 1 -> L2 -> Ln - 2 -> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

This problem combines multiple linked list techniques: finding the middle (fast & slow pointers), reversing the second half, and merging two lists. It's an excellent exercise in breaking down a complex problem into simpler sub-problems.

Example 1

Input: head = [1,2,3,4]
Output: [1,4,2,3]
Explanation: The list is reordered by interleaving nodes from the beginning and end.

Example 2

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: For odd-length lists, the middle node stays in the middle after reordering.

Constraints

  • •The number of nodes in the list is in the range [1, 5 * 10^4]
  • •1 <= Node.val <= 1000
Show Hints (4)
Hint 1: This problem can be broken into three sub-problems. What are they?
Hint 2: First sub-problem: How can you find the middle of the linked list efficiently?
Hint 3: Second sub-problem: Once you have the second half, what operation allows you to access nodes from the end easily?
Hint 4: Third sub-problem: Now you have the first half and a reversed second half. How do you merge them to get the desired order?
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?