Odd Positions First

Medium

You get a singly linked list head. Number the nodes from one: the first node is at an odd position, the second at an even one, and so on. Rearrange the list so that all nodes from odd positions come first, followed by all nodes from even positions. Within each group, nodes keep their original order. Return the head of the resulting list. Try to use O(1) extra memory and O(n) time: relink the existing nodes instead of creating new ones.

Example 1

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

Positions 1, 3, 5 hold 7, 9, 4 and positions 2, 4, 6 hold 3, 1, 8. The first group goes first, then the second.

Example 2

head=list_node([5, -2]) → [5, -2]

Two nodes are already in the right order.

Example 3

head=list_node([]) → None

An empty list stays empty.

Constraints

The list has between 0 and 10⁴ nodes
-10⁶ ≤ Node.val ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List

Similar problems

Adding Digit Lists Medium Drop the K-th Node From the Tail Medium Trade Places in Twos Medium Move the Tail to the Front Medium Sorted List, Unique Values Only Medium

Input

head=list_node([7, 3, 9, 1, 4, 8])

Expected

[7, 9, 4, 3, 1, 8]

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