Problem
Given the head of a singly linked list, group all the nodes at odd indices together followed by the nodes at even indices, and return the reordered list.The first node is considered to be at index
1. The relative order of the nodes within the odd and even groups should remain the same.
Example(s)
Consider the following examples to understand the expected input and output.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]Solution
This solution uses two pointers to maintain separate odd and even linked lists. Theodd pointer connects nodes at odd positions, while the even pointer connects nodes at even positions.
We move both pointers forward together. After processing all nodes, we connect the end of the odd list to the beginning of the even list. This rearranges the list in-place while preserving the relative order within each group.
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
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;
}
}Complexity
Each node is processed once, so the time complexity isO(n), where n is the number of nodes in the linked list.
The list is rearranged in-place using only a few pointers, so the extra space complexity is
O(1).