Odd Even Linked List

1. Define the problem

Rearrange a linked list so that all the nodes sitting in odd positions come first, followed by all the nodes in even positions . Positions are counted from 1 at the head, and they have nothing to do with whether the stored numbers are odd or even. Inside each group the nodes must keep the order they already had. The function takes a plain array, builds the list inside, and returns a plain array. Build two chains at once — one collecting the odd-position nodes and one collecting the even-position nodes — by hopping two steps at a time, then join the end of the odd chain to the start of the even chain.

Constraints

The number of nodes is between 0 and 10⁴
-10⁶ ≤ node value ≤ 10⁶
The relative order inside each group must be preserved
The rearranging must use only a fixed amount of extra memory

Example

Inputvalues = [1, 2, 3, 4, 5]

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

Explanation Positions 1, 3 and 5 hold 1, 3 and 5, so they come first. Positions 2 and 4 hold 2 and 4, so they follow.

2. Know the words first

In plain terms

Position in the list: The count of a node from the head, starting at 1. The head is position 1, the node after it is position 2, and so on.
Relinking: Changing which node a next pointer aims at. No node is copied or created; only the arrows between existing nodes move.
Even head: A saved pointer to the first even-position node. You must save it at the start, because once the odd chain is rebuilt you can no longer find it by walking.

3. Visualize the solution

Each cell is one node in its original position, head first

n11

n22

n33

n44

n55

Statusinit

odd starts on node 1, even starts on node 2, and node 2 is saved as the even head.

What happens in this step

list = 1 -> 2 -> 3 -> 4 -> 5
odd = node 1
even = node 2
evenHead = node 2 (saved for the very last step)

Two chains will now be pulled apart from this single list.

Step 1 of 6

Steps to visualize

The cells never move; only the arrows between them change.
The odd pointer walks positions 1, 3, 5… and the even pointer walks positions 2, 4, 6…
Each round links the odd pointer to the node after the even one, then links the even pointer to the node after that.
The walk stops when the even pointer runs off the end of the list.
Finally the end of the odd chain is joined to the saved first even node.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell is one node in its original position, head first

n11

n22

n33

n44

n55

Statusinit

odd starts on node 1, even starts on node 2, and node 2 is saved as the even head.

What happens in this step

list = 1 -> 2 -> 3 -> 4 -> 5
odd = node 1
even = node 2
evenHead = node 2 (saved for the very last step)

Two chains will now be pulled apart from this single list.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function toList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = new ListNode(values[i], head);
  }
  return head;
}

function toArray(head) {
  const out = [];
  for (let node = head; node !== null; node = node.next) {
    out.push(node.val);
  }
  return out;
}

function oddEvenList(values) {
  const head = toList(values);
  if (head === null || head.next === null) {
    return toArray(head);
  }

  let odd = head;
  let even = head.next;
  const evenHead = even;

  while (even !== null && even.next !== null) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }

  odd.next = evenHead;
  return toArray(head);
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 2, 3, 4, 5]`	`[1, 3, 5, 2, 4]`	example from the description, odd node count
`values = [1, 2, 3, 4]`	`[1, 3, 2, 4]`	an even number of nodes
`values = []`	`[]`	empty list, nothing to rearrange
`values = [9]`	`[9]`	a single node, which is already finished
`values = [1, 2]`	`[1, 2]`	two nodes, one in each group
`values = [2, 1, 3, 5, 6, 4, 7]`	`[2, 3, 6, 7, 1, 5, 4]`	values out of order, to show positions matter rather than values

Odd Even Linked List