Reorder List
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Rearrange L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... in place.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1The final order takes nodes from the front and the back alternately. Which half would you like to read backwards?
- Hint 2Combine three tools you know: middle node, reverse list, and merging two lists by alternating.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Shuffle a deck by hand: split it into two halves, flip the second half upside down, then take one card from the top of each half alternately. On a linked list there is no card-flipping, so you do these exact three moves with pointers: find the middle, reverse the back half, and weave the two halves together.
- The obvious way
Put all nodes in an array and rebuild the links by index: O(n) extra memory.
- The key insight
Do it in three steps, in place. (1) Find the middle with fast and slow pointers. (2) Cut the list there and reverse the second half. (3) Zip: take one node from the first half, then one from the reversed second half, repeating until the second half is used up.
- The algorithm
- Find the middle (slow/fast pointers).
- Cut the list after the middle; reverse the second half.
- Take a node from the first half, then one from the reversed half, linking them alternately.
- Stop when the reversed half is finished.
Watch it run
Examplelist = 1 -> 2 -> 3 -> 4
Find the middle: the first half is 1 -> 2 and the second half is 3 -> 4.
halves: [1, 2] and [3, 4]
Where people slip
- Cut the first half's end (slow.next = None) before zipping, or you create a loop.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def reorder_list(head):
if not head or not head.next:
return
slow, fast = head, head # 1. find the middle
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next # 2. cut and reverse the second half
slow.next = None
previous = None
while second:
next_node = second.next
second.next = previous
previous, second = second, next_node
first, second = head, previous # 3. zip the halves together
while second:
first_next, second_next = first.next, second.next
first.next = second
second.next = first_next
first, second = first_next, second_nextNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.