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 <= 106This 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.
The code begins by checking if the list is empty or just a single node, in which case it simply returns the list as is. Two pointers, 'odd' and 'even', are initialized to the first and second nodes, respectively. The 'evenHead' pointer is used to remember the start of the even index list. We then iterate through the list, linking odd nodes to the next odd nodes and even nodes to the next even nodes. Finally, odd nodes are linked to the 'evenHead'.
C++
Java
Python
C#
JavaScript
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Two Pointers Approach | 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. |
| Recursive Approach | 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. |
L6. Odd Even Linked List | Multiple Approaches • take U forward • 147,889 views views
Watch 9 more video solutions →Practice Odd Even Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor