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.
Here’s the [Problem Link] to begin with.
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]
Constraints:
- The number of nodes in the linked list is in the range
[0, 104]. -106 <= Node.val <= 106
Solution 1: Brute Force Approach (Using Array)
Intuition
Think of this like organizing a line of people! You want all the people in odd positions (1st, 3rd, 5th…) to go first, then all the people in even positions (2nd, 4th, 6th…) to follow. One simple way is to write down all the odd-position people’s names first, then all the even-position people’s names, and finally rearrange everyone according to your list.
Detailed Approach
- First Pass: Walk through the linked list and collect all values from odd-positioned nodes (1st, 3rd, 5th…)
- Second Pass: Walk through the linked list again and collect all values from even-positioned nodes (2nd, 4th, 6th…)
- Combine Arrays: Now we have all odd-position values followed by all even-position values
- Third Pass: Walk through the original linked list and replace each node’s value with values from our combined array
- Return Result: The linked list now has the desired odd-even arrangement
Code
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head # Empty list or single node - nothing to rearrange
temp = head
values = []
# First pass: Collecting values from odd-indexed nodes (1st, 3rd, 5th, ...)
while temp:
values.append(temp.val) # Add current node's value
if temp.next:
temp = temp.next.next # Skip one node to get next odd position
else:
break # Reached end of list
temp = head.next # Start from 2nd node (first even position)
# Second pass: Collecting values from even-indexed nodes (2nd, 4th, 6th, ...)
while temp:
values.append(temp.val) # Add current node's value
if temp.next:
temp = temp.next.next # Skip one node to get next even position
else:
break # Reached end of list
# Third pass: Assigning collected values back to the nodes
index = 0
temp = head
while temp:
temp.val = values[index] # Replace node value with rearranged value
index += 1
temp = temp.next
return headCode Explanation
We use three separate passes through the linked list. In the first pass, we start from the head (1st node) and jump two nodes at a time to collect all odd-positioned values. In the second pass, we start from the second node and again jump two nodes at a time to collect all even-positioned values. Now our array has all odd values followed by all even values in the correct order. In the third pass, we simply replace each node’s value with the values from our rearranged array.
Dry Run
Let’s trace through: 1 -> 2 -> 3 -> 4 -> 5
First Pass (Odd positions):
- Start at node 1: values = , jump to node 3
- At node 3: values = , jump to node 5
- At node 5: values = , no more nodes
Second Pass (Even positions):
Third Pass (Replace values):
- Node 1: value = 1 (values)
- Node 2: value = 3 (values)
- Node 3: value = 5 (values)
- Node 4: value = 2 (values)
- Node 5: value = 4 (values)
Result: 1 -> 3 -> 5 -> 2 -> 4
Time and Space Complexity
- Time Complexity: O(n) – We traverse the list three times, but it’s still linear
- Space Complexity: O(n) – We store all node values in the array
Simplifying It
This approach is like making a guest list for a party – first write down all the odd-numbered guests, then all the even-numbered guests, and finally rearrange everyone according to your list. It’s easy to understand but requires extra space to store all the values.
Solution 2: Optimal Approach (Pointer Manipulation)
Intuition
Instead of writing down names and rearranging, what if we could just change who’s standing next to whom? Imagine you have two group leaders – one for odd positions and one for even positions. Each leader collects their group members by changing the hand-holding pattern. At the end, the odd group leader connects their group to the even group!
Detailed Approach
- Set Up Group Leaders: Create two pointers – one for odd positions starting at head, one for even positions starting at head.next
- Remember Even Start: Keep track of where the even group starts so we can connect it later
- Collect Odd Group: Make odd pointer jump two nodes at a time, connecting only odd-positioned nodes
- Collect Even Group: Make even pointer jump two nodes at a time, connecting only even-positioned nodes
- Connect Groups: Connect the end of the odd group to the beginning of the even group
Code
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head # Empty list or single node - nothing to rearrange
odd = head # Pointer for odd-positioned nodes
even = head.next # Pointer for even-positioned nodes
even_head = even # Remember where even group starts
# Traverse the list, rearranging odd and even nodes
while even and even.next:
odd.next = odd.next.next # Connect current odd to next odd
odd = odd.next # Move odd pointer forward
even.next = even.next.next # Connect current even to next even
even = even.next # Move even pointer forward
# Append the even list to the end of the odd list
odd.next = even_head
return headCode Explanation
We use two pointers to build two separate chains – one for odd positions and one for even positions. The odd pointer starts at the head and connects every odd-positioned node by skipping the even ones. Similarly, the even pointer starts at the second node and connects every even-positioned node by skipping the odd ones. We continue this until we reach the end of the list. Finally, we connect the end of the odd chain to the beginning of the even chain, creating the desired arrangement.
Dry Run
Let’s trace through: 1 -> 2 -> 3 -> 4 -> 5
Initial Setup:
- odd = 1, even = 2, even_head = 2
- Current state:
1 -> 2 -> 3 -> 4 -> 5
Step 1:
- odd.next = 3 (skip node 2):
1 -> 3 -> 4 -> 5, odd = 3 - even.next = 4 (skip node 3):
2 -> 4 -> 5, even = 4 - Current odd chain:
1 -> 3, Current even chain:2 -> 4
Step 2:
- odd.next = 5 (skip node 4): odd chain becomes
1 -> 3 -> 5, odd = 5 - even.next = None (no more nodes): even chain becomes
2 -> 4, even = None
Final Connection:
- odd.next = even_head: Connect
1 -> 3 -> 5to2 -> 4 - Final result:
1 -> 3 -> 5 -> 2 -> 4
Result: 1 -> 3 -> 5 -> 2 -> 4
Time and Space Complexity
- Time Complexity: O(n) – We traverse the list once
- Space Complexity: O(1) – We only use a few pointer variables
Simplifying It
This approach is like having two team captains who pick their team members alternately, but instead of moving people around, they just change who’s holding whose hand. Much more efficient since we don’t need extra space – we just rewire the connections!
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Array) | O(n) | O(n) | Easy | Learning the concept |
| Optimal (Pointer Manipulation) | O(n) | O(1) | Medium | Production code |
The optimal approach is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you’re first learning about linked list manipulation.
Both solutions effectively solve the problem, but the optimal solution showcases advanced pointer manipulation techniques that are valuable for solving many other linked list problems. The key insight is that we don’t need to store values separately, we can just rewire the connections between nodes!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
