List Folded From Both Ends

Medium

You are given the head head of a non-empty singly linked list. Call its nodes, in order, A₀ → A₁ → … → Aₖ. Rearrange the list so that the nodes go in the order A₀ → Aₖ → A₁ → Aₖ₋₁ → A₂ → Aₖ₋₂ → … that is, alternately the first remaining node from the front and the last remaining node from the back. You may not change the values stored in the nodes, only move the nodes themselves by changing their next links. Return the head of the resulting list.

Example 1

head=list_node([10, 20, 30, 40, 50, 60]) → [10, 60, 20, 50, 30, 40]

Nodes are taken alternately from the front and the back: 10, 60, 20, 50, 30, 40. The values stay put; only the links change.

Example 2

head=list_node([7, 3, 9]) → [7, 9, 3]

The list becomes 7 → 9 → 3: the middle node ends up last.

Example 3

head=list_node([5]) → [5]

Constraints

The list has between 1 and 5 · 10⁴ nodes
1 ≤ Node.val ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Recursion Linked List Two Pointers

Similar problems

Symmetric Bead String Easy Mirror Pairs in a List Medium Leaders of a List Medium Adding Digit Lists Medium Drop the K-th Node From the Tail Medium

Input

head=list_node([10, 20, 30, 40, 50, 60])

Expected

[10, 60, 20, 50, 30, 40]

Run checks the first 3 tests in your browser. Submit checks all 33 tests on the server, hidden ones included.