Statement▼
Given the head of a singly linked list, rearrange the nodes so that all nodes at odd indexes appear first, followed by all nodes at even indexes.
The first node in the list is considered at odd index 1, the second at even index 2, and so on.
Within the odd group and the even group, the relative order of the nodes must remain the same as in the original list.
Return the head of the reordered linked list.
Note: You must solve the problem in
O(1) extra space complexity andO(n) time complexity.
Constraints:
The number of nodes in the linked list is in the range
[0,103] .−103≤ Node.val≤103
Solution
This problem requires us to reorder a singly linked list by grouping all odd-indexed nodes, followed by all even-indexed nodes. The key constraints are to perform this modification in place, using
The solution’s essence is to partition the linked list into two separate lists, one for odd-indexed nodes and one for even-indexed nodes, and then link them together. This is done in place by carefully reassigning the next pointers.
We establish three key pointers to manage the process:
We use an
oddpointer starting at head (the first node) and anevenpointer starting athead.next(the second node).We also save the head of the
evenlist (evenHead = head.next) because we’ll need to connect the end of theoddlist to it later.
The following steps can be performed to implement the algorithm above:
We use an
oddpointer starting athead(the first node) and anevenpointer starting athead.next(the second node).We also save the head of the even list (
evenHead = head.next) because we’ll need to connect the end of the odd list to it later.We traverse the linked list, and in each step, we re-link the nodes:
The current
oddnode’snextis set to skip the adjacentevennode and point to the next odd node (odd.next = even.next).The current
evennode’snextis set to skip the new adjacentoddnode and point to the next even node (even.next = odd.next).
This process effectively unlinks the even nodes from the odd chain and links them into their own chain, while simultaneously connecting the odd nodes.
After the loop terminates, the
oddpointer will be at the tail of the odd-indexed list.We connect this tail to the saved head of the even-indexed list (
odd.next = evenHead). This rewires the entire list in-place to meet the problem’s requirements.
Let’s look at the following illustration to get a better understanding of the solution: