PPractick

The problem

A printing queue interleaves jobs from two departments: positions 1, 3, 5, ... belong to Finance and positions 2, 4, 6, ... to Marketing. The manager wants all of Finance's jobs first, then all of Marketing's, each group keeping its original relative order, and the reshuffle must happen in place with O(1) extra memory. Two pointers do it by threading two chains, one through the odd-position nodes and one through the even-position nodes, and then joining the end of the odd chain to the start of the even chain.

Example: 1 -> 2 -> 3 -> 4 -> 5 → 1 -> 3 -> 5 -> 2 -> 4.

Function signature

Node* oddEvenList(Node* head);  // odd positions (1st, 3rd, ...) first, then even positions

Test cases

Input list	Output list	Explanation
1 -> 2 -> 3 -> 4 -> 5	1 -> 3 -> 5 -> 2 -> 4
2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7	2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4	Positions, not values, decide the group
1 -> 2	1 -> 2	Already grouped
1	1
(empty)	(empty)

(Confirm: "odd" and "even" refer to 1-indexed positions, not values (LeetCode 328); relative order within each group is preserved.)

How interviewers phrase it

• "Group all odd-indexed nodes together followed by the even-indexed nodes" (LeetCode 328).
• A value-based variant: "segregate even and odd values" (GeeksforGeeks), solved by the same chain-building idea with a different test.

Clarifying questions to ask

1. Odd and even by position or by value?
2. Is the first node position 1 (odd)?
3. Must it be O(1) extra space?

Follow-ups to expect

1. "Why keep a pointer to the first even node?"
2. "What's the loop condition?"
3. "How would you segregate by value instead?"
4. "Complexity?"

Related questions

• Search in Linked List Medium
• Reverse a Doubly Linked List Medium
• Reverse a LinkedList [Iterative] Medium
• Reverse a LL Medium
• Detect a loop in LL Medium
• Find the starting point in LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in