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.
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:
[0, 104].-106 <= Node.val <= 106The key idea in Odd Even Linked List is to rearrange nodes so that all nodes at odd indices appear first, followed by nodes at even indices, while preserving their original relative order. Instead of creating new nodes or using extra storage, the optimal strategy modifies the existing next pointers directly.
A common approach is to maintain two pointers: one for the odd-positioned nodes and another for the even-positioned nodes. You also store the head of the even list so it can be attached after the odd list at the end. During traversal, update the next links to skip alternating nodes, effectively building two separate chains within the same list.
After processing all nodes, connect the last odd node to the head of the even list. This technique processes the list in a single pass, achieving O(n) time complexity with O(1) extra space since only a few pointers are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two-pointer in-place rearrangement | O(n) | O(1) |
take U forward
This approach uses two pointers to manage odd and even indexed nodes separately. We maintain separate pointers for the head of the odd and even lists and iterate through the given list. As we go along, we link odd indices to the next odd and even indices to the next even. In the end, we connect the last odd indexed node to the head of the even indexed list.
Time Complexity is O(n) since we traverse the entire list once. Space Complexity is O(1) because we're rearranging pointers without using any extra space for storage.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public ListNode OddEvenList(ListNode head) {
9 if (head == null || head.next == null) return head;
10
11 ListNode odd = head;
12 ListNode even = head.next;
13 ListNode evenHead = even;
14
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}C# implementation starts with a check for null or single-node list, returning as is. It initializes two pointers, 'odd' and 'even', and another 'evenHead' for remembering even node starts. Through looping, odd and even nodes are rearranged, and finally, the odd nodes' tail connects to the even starts, preserving order within the segregated lists.
Although not typical due to O(1) space requirement, this problem could conceptually be solved recursively by defining a function that processes the head and its next elements recursively, managing pointers for odd and even segments. As recursion inherently uses extra space on the stack, this isn't space-optimal, thus academically interesting but not compliable with constant space constraints.
Time Complexity remains O(n) for full list traversal. However, Space Complexity rises to O(n) because of the call stack in recursion, unsuitable under given problem constraints for constant space.
1class ListNode:
2 def __init__(self, val=0,
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, linked list manipulation problems like Odd Even Linked List frequently appear in technical interviews at companies such as Amazon, Google, and Meta. They test pointer handling, in-place operations, and understanding of linked list traversal.
The optimal approach uses two pointers to separate odd and even indexed nodes while traversing the list once. By adjusting the next pointers in-place and reconnecting the lists at the end, the problem can be solved in linear time with constant extra space.
A singly linked list structure with pointer manipulation is sufficient. The solution relies on maintaining references to odd and even nodes and updating next pointers rather than using additional data structures.
The even head pointer stores the start of the even-indexed nodes while rearranging the list. After all odd nodes are linked together, this saved pointer allows the algorithm to attach the even list to the end efficiently.
This Python solution uses a local function 'partition' which recursively treats nodes as alternating odd or even. Despite functional recursion achieving the same odd-even connection, it ruins constant space by occupying stack memory, which might exceed constraints under deep recursion.