
Description
Given a singly linked list, we need to group all odd-indexed nodes together followed by the even-indexed nodes. The first node is considered odd, the second node is even, and so on. The relative order inside both the odd and even groups should remain as it was in the input. The goal is to achieve this in O(1) space complexity and O(n) time complexity.
Intuition
The problem can be visualized as rearranging the linked list into two sublists: one containing all odd-indexed nodes and the other containing all even-indexed nodes. Once we have these two sublists, we can simply concatenate the even sublist at the end of the odd sublist.
Approach
- Initial Setup:
- Check if the list is empty or has less than three nodes; if so, return the head as it is.
- Initialize two pointers:
odd
pointing to the first node andeven
pointing to the second node. Keep a reference to the head of the even sublist (evenHead
), as we'll need to append it at the end. - Reordering:
- Traverse the list, where the
odd
pointer skips to the next odd node and theeven
pointer skips to the next even node. - If the next odd node exists, update theodd
pointer to point to it, otherwise stop. - If the next even node exists, update theeven
pointer to point to it, otherwise stop. - Concatenation:
- Once the traversal is complete, link the last odd node to the head of the even sublist.
- Set the last node of the even sublist to
None
to terminate the list. - Return: - Return the modified head of the list.
Complexity
Time Complexity:
O(n), where n is the number of nodes in the linked list. The list is traversed only once.
Space Complexity:
O(1), since we are rearranging the nodes in place and not using any extra space other than a few pointers.
Code
C++
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next || !head->next->next)
return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
bool oddIncrement = true, evenIncrement = true;
while (odd && even && (oddIncrement || evenIncrement)) {
if (odd->next && odd->next->next) {
odd->next = odd->next->next;
odd = odd->next;
} else {
oddIncrement = false;
}
if (even->next && even->next->next) {
even->next = even->next->next;
even = even->next;
} else {
evenIncrement = false;
}
}
odd->next = evenHead;
even->next = nullptr;
return head;
}
};
Python
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next or not head.next.next:
return head
odd = head
even = head.next
even_head = even
odd_increment = True
even_increment = True
while odd and even and (odd_increment or even_increment):
if odd.next and odd.next.next:
odd.next = odd.next.next
odd = odd.next
else:
odd_increment = False
if even.next and even.next.next:
even.next = even.next.next
even = even.next
else:
even_increment = False
odd.next = even_head
even.next = None
return head
Java
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null)
return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
boolean oddIncrement = true, evenIncrement = true;
while (odd != null && even != null && (oddIncrement || evenIncrement)) {
if (odd.next != null && odd.next.next != null) {
odd.next = odd.next.next;
odd = odd.next;
} else {
oddIncrement = false;
}
if (even.next != null && even.next.next != null) {
even.next = even.next.next;
even = even.next;
} else {
evenIncrement = false;
}
}
odd.next = evenHead;
even.next = null;
return head;
}
}
JavaScript
var oddEvenList = function(head) {
if (!head || !head.next || !head.next.next)
return head;
let odd = head, even = head.next, evenHead = even, oddIncrement = true, evenIncrement = true;
while (odd && even && (oddIncrement || evenIncrement)) {
if (odd.next && odd.next.next) {
odd.next = odd.next.next;
odd = odd.next;
} else
oddIncrement = false;
if (even.next && even.next.next) {
even.next = even.next.next;
even = even.next;
} else
evenIncrement = false;
}
odd.next = evenHead;
even.next = null;
return head;
};