Interleave a Linked List from Both Ends | Practice

You are given head, the first node of a singly linked list.

Rearrange the nodes in place so they come in the order first, last, second, second to last, third, third to last, and so on: the list A → B → C → D → E becomes A → E → B → D → C. Change the next pointers only, not the values, and return nothing; the answer is read from head.

Linked lists are written as their values from head to tail, so [1, 4, 6] is 1 → 4 → 6.

Example 1

Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Example 2

Input: head = [10, 20, 30, 40, 50]
Output: [10, 50, 20, 40, 30]

With an odd number of nodes, the middle one ends up last.

Constraints

The list holds 1 to 5000 nodes.
Every value is between 1 and 1000.

Show the pattern

Linked list

You need the back half's nodes in reverse order, but a singly linked list only walks forwards. Find the middle with fast and slow pointers, reverse the back half in place, then weave the two halves together.

See linked list in a visualiser

Show the approach

Three steps, all in place:

Find the middle. Move slow one node and fast two nodes at a time until fast can't move two more. slow is then the last node of the front half.
Reverse the back half. Cut the list after slow and reverse the nodes after it, as in reversing a linked list.
Weave. Take the first node of each half in turn, saving both next pointers before relinking.

The front half has as many nodes as the back half, or one more, so with an odd count the middle node ends up last.

Time: O(n) · Space: O(1)

Brush up firstLinked List visualiser