Skip to main content

328. Odd Even Linked List

medium

Group all nodes at odd positions before all nodes at even positions, in place, with O(1) extra space. The two-tail interleave: one pointer walks the odds, one walks the evens, and after the loop you stitch them.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input. You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Constraints

  • The number of nodes in the linked list is in the range [0, 10^4].
  • -10^6 <= Node.val <= 10^6

Examples

Example 1

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

Example 2

Input
head = [2,1,3,5,6,4,7]
Output
[2,3,6,7,1,5,4]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Maintain two tail pointers: odd (starts at head) and even (starts at head.next). Also stash evenHead = head.next so you can reattach it later.

Hint 2

Inside the loop, do odd.next = odd.next.next, then advance odd; do even.next = even.next.next, then advance even. The two chains weave forward through the original list.

Hint 3

After the loop, odd is at the tail of the odd chain. Stitch odd.next = evenHead and you're done.

Solution approach

Reveal approach

Two-tail in-place interleave. Handle the trivial case (null or single node) up front by returning head. Otherwise initialize odd = head, even = head.next, evenHead = even (so you can stitch later). Loop while even and even.next are both non-null: odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next. Each iteration consumes two nodes from the original list and appends one to the odd chain and one to the even chain. After the loop, the odd chain's tail is odd and the even chain is already terminated (because even.next was already null when the loop ended) — stitch them with odd.next = evenHead. Return head. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • two-pointers
  • pointer-rewiring

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Odd Even Linked List and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →