Odd Slots Then Even Slots

MediumLinked List

Problem

A conveyor belt is modelled as a singly linked list. Number its positions from 1. The packing robot wants every item in an odd position first, followed by every item in an even position.

Given the head, regroup the nodes accordingly, keeping the relative order inside each group, and return the head. Use O(1) extra space.

Example 1

Input:
head = [10, 20, 30, 40, 50]
Output:
[10, 30, 50, 20, 40]

Positions 1, 3, 5 hold 10, 30, 50; positions 2, 4 hold 20, 40.

Example 2

Input:
head = [4, 1, 4, 1]
Output:
[4, 4, 1, 1]

Constraints

  • 0 ≤ number of nodes ≤ 10^4
  • -10^6 ≤ node.val ≤ 10^6
  • Positions count from 1; it is about positions, not values.

Hint

Show the first hint

Think of it as splitting the list into two lists and then joining them.

Walkthrough

How to approach it

01Clarify before coding

  • Odd and even by position or by value? By position, starting at 1.
  • Keep relative order inside each group? Yes.
  • Can I allocate new nodes? No, relink the existing ones with O(1) extra space.

02Brute force

Copy the values at odd positions, then those at even positions, into an array and write them back.

Cost: O(n) time and O(n) extra space, and it moves values instead of nodes.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.