All problems

Odd Even Linked List

Medium · linked list

You are given the head of a singly linked list. Number the nodes from 1 starting at the head, so the head is position 1, the next node is position 2, and so on.

Rearrange the list so that every node at an odd position comes first, followed by every node at an even position. Inside each group the nodes keep the order they had in the original list. Return the head of the rearranged list.

The groups depend on the position of a node, not on its value. An empty list stays empty. The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

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

Output: [1, 3, 5, 2, 4]

Positions 1, 3 and 5 hold 1, 3 and 5; positions 2 and 4 hold 2 and 4.

Example 2

Input: head = [6, 9, 4, 7]

Output: [6, 4, 9, 7]

The odd positions hold 6 and 4, the even positions hold 9 and 7. The values themselves are irrelevant.

Example 3

Input: head = [3]

Output: [3]

Constraints