Question
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 on 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 is a linked_list question.
Idea
- Use a fast and slow pointer to find the second half of the list
- Reverse the second half of the list
- While second list still has nodes (of equal or greater lengths than the first list)
- Temporarily store the next nodes of both lists
- Set the next node of the first list to the head of the second list
- Set the next node of the second list to the temp variable that held the next node of the first list (this is kind of like a weaving pattern)
- Set first list and second list to their temp variables, effectively moving the heads one node down the list