Dare2Solve
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.
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.
Initial Setup:
odd
pointing to the first node and even
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:
odd
pointer skips to the next odd node and the even
pointer skips to the next even node.odd
pointer to point to it, otherwise stop.even
pointer to point to it, otherwise stop.Concatenation:
None
to terminate the list.Return:
O(n), where n is the number of nodes in the linked list. The list is traversed only once.
O(1), since we are rearranging the nodes in place and not using any extra space other than a few pointers.
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;
}
};
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
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;
}
}
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;
};