Reorder List
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
Given the head of a linked list with nodes L0, L1, ..., Ln, rearrange its nodes in place to weave the list from the outside in: L0, Ln, L1, Ln - 1, L2, Ln - 2, ...
Rewire the existing nodes rather than creating new ones, and return the head of the reordered list.
Input: head = [1 -> 2 -> 3 -> 4]
Output: [1 -> 4 -> 2 -> 3]
Input: head = [1 -> 2 -> 3 -> 4 -> 5]
Output: [1 -> 5 -> 2 -> 4 -> 3]
Input: head = [1]
Output: [1]
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
What does reordering head = [2 -> 4 -> 6 -> 8 -> 10] produce?
[2 -> 10 -> 4 -> 8 -> 6]
[10 -> 8 -> 6 -> 4 -> 2]
[2 -> 4 -> 10 -> 6 -> 8]
[2 -> 6 -> 4 -> 10 -> 8]
Take a moment to understand the problem and think of your approach before you start coding.