AlgoViz
HomeLinked List

Segregate odd and even nodes in Linked List

Medium

Weave two chains, then join them

Problem

Given the head of a linked list, group all nodes at odd positions together followed by the nodes at even positions, keeping their relative order. Return the head.

In simple words

Weave two chains — one of odd-position nodes, one of even — then join them end to end.

The idea

Build one chain from the odd-position nodes and another from the even ones by advancing each by two, then attach the even chain to the tail of the odd chain. Keeping a reference to the even head before you start is what lets you reattach at the end.

The trick

  • Save the even head first — you will need it after the weave.
  • Terminate the even chain with null or you create a cycle.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
0
1
2
3
4

Step 1 of 2. Here's the example — head = [1, 2, 3, 4, 5] Values: 1, 2, 3, 4, 5.

1/2
Optimal
timeO(n)spaceO(1)
1odd = head; even = head.next; evenHead = even2while even and even.next:3  odd.next = even.next; odd = odd.next4  even.next = odd.next; even = even.next5odd.next = evenHead6return head

Input

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

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4 -> 5
Output:
1 -> 3 -> 5 -> 2 -> 4
Explanation:
Odd-position nodes first, then even-position ones.

Example 2

Input:
list = 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
Output:
2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
Explanation:
Group by position, keeping order.

Example 3

Input:
list = 1 -> 2
Output:
1 -> 2
Explanation:
One odd, one even.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.