Rearrange a LinkedList

Hard·Tagslinked-listtwo-pointers

Problem Statement

Given the head of a Singly LinkedList, write a method to modify the LinkedList such that the nodes from the second half of the LinkedList are inserted alternately to the nodes from the first half in reverse order. So if the LinkedList has nodes L0 -> L1 -> ... -> Ln-1 -> Ln, its reordered form will be L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... You must not alter the values in the list's nodes. Only the nodes themselves may be changed.

Examples

Example 1

Input

head: [2, 4, 6, 8, 10, 12]

Linked list

Output

"[2, 12, 4, 10, 6, 8]"

Why

We split the list at the middle (2,4,6 and 8,10,12), reverse the second half (12,10,8), and merge them alternately.

Example 2

Input

head: [2, 4, 6, 8, 10]

Linked list

Output

"[2, 10, 4, 8, 6]"

Why

For an odd number of nodes, the middle node (6) ends up at the very end of the reordered list.

Constraints

•1 <= Number of Nodes <= 10000
•1 <= Node.val <= 100000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A brute-force approach could involve storing all nodes in an array so you can access them via an index, but that takes O(N) space. Can you do it in O(1) space?

Hint 2

This problem is a combination of three distinct Linked List operations.

Hint 3

First, use the Fast and Slow pointers method to find the middle of the linked list.

Hint 4

Second, reverse the second half of the linked list in-place.

Hint 5

Third, iterate through the first half and the reversed second half simultaneously, weaving the nodes together one by one.