/328. Odd Even Linked List
Previous|Next

328. Odd Even Linked List

Medium
Linked Lists62.4% acceptance

Given the head node of a singly linked list, rearrange the nodes so that all nodes at odd indices (1-based) appear first, followed by all nodes at even indices. The relative order of nodes within the odd and even groups must remain unchanged. Return the head node of the reordered list.

Example 1

Input: ListNode(10, ListNode(20, ListNode(30, ListNode(40, ListNode(50)))))

Output: [10, 30, 50, 20, 40]

Explanation: Odd indices: 10, 30, 50; Even indices: 20, 40.

Example 2

Input: ListNode(5, ListNode(7, ListNode(9)))

Output: [5, 9, 7]

Explanation: Odd indices: 5, 9; Even indices: 7.

Example 3

Input: ListNode(1, ListNode(2))

Output: [1, 2]

Explanation: Odd indices: 1; Even indices: 2.

Example 4

Input: None

Output: []

Explanation: Empty list returns empty.

Constraints

  • 0 <= number of nodes <= 10_000
  • -1_000_000 <= node value <= 1_000_000
  • Input is a singly linked list
  • Must use O(1) extra space
  • Must run in O(n) time
Python (current runtime)

Case 1

Input: ListNode(8, ListNode(6, ListNode(4, ListNode(2, ListNode(0)))))

Expected: [8, 4, 0, 6, 2]

Case 2

Input: ListNode(3, ListNode(1, ListNode(4, ListNode(1, ListNode(5, ListNode(9))))))

Expected: [3, 4, 5, 1, 1, 9]

Case 3

Input: ListNode(42)

Expected: [42]

Case 4

Input: ListNode(-1, ListNode(-2, ListNode(-3, ListNode(-4))))

Expected: [-1, -3, -2, -4]