Description
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.
Examples:
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 in Python
To solve the problem of grouping nodes of a singly linked list into odd and even indexed groups, we can implement the following approach in Python. The main goal is to maintain two separate lists during the traversal: one for odd-indexed nodes and one for even-indexed nodes. After we’ve processed all nodes, we reconnect the two lists.
Plan:
- We will maintain two pointers:
- odd pointer: points to the current odd-indexed node.
- even pointer: points to the current even-indexed node.
- Traverse the linked list, alternating between odd and even nodes, until the list ends.
- After traversing, reconnect the odd list with the even list by linking the last odd node to the head of the even list.
- Return the modified linked list.
Python
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# If the list is empty or has only one node, return the list as it is
if not head or not head.next:
return head
# Initialize two pointers: odd for the odd-indexed nodes, and even for the even-indexed nodes
odd = head # First node (head) is considered odd
even = head.next # Second node is even
even_head = even # We need to save the head of the even list to reconnect later
# Traverse the list, adjusting the next pointers for odd and even lists
while even and even.next:
# The next odd node is the one after the current even node
odd.next = even.next
odd = odd.next # Move the odd pointer to the next odd node
# The next even node is the one after the current odd node
even.next = odd.next
even = even.next # Move the even pointer to the next even node
# After all odd nodes, connect the end of the odd list to the head of the even list
odd.next = even_head
# Return the reordered list starting from the head (first odd node)
return headExplanation:
- Base Case:
- If the list is empty or has only one node, there’s nothing to reorder, so we return the list as it is.
- Pointer Initialization:
- We start with two pointers:
oddpointing to the first node (head), which is the first odd-indexed node.evenpointing to the second node (head.next), which is the first even-indexed node.
- We also store the head of the even list in
even_headbecause later we will need to attach the odd list to the even list.
- We start with two pointers:
- Traversal:
- We iterate through the list as long as both
evenandeven.nextare notNone. This ensures that we can always link the next odd and even nodes correctly. - For each iteration, we:
- Move the
odd.nexttoeven.next(linking the odd nodes). - Move the
even.nexttoodd.next(linking the even nodes).
- Move the
- This alternates between processing odd and even nodes, maintaining the relative order within each group.
- We iterate through the list as long as both
- Reconnecting the Lists:
- After the traversal, the odd and even nodes are separated. The last odd node should point to the head of the even list, stored in
even_head, to merge the two sub-lists together.
- After the traversal, the odd and even nodes are separated. The last odd node should point to the head of the even list, stored in
- Return:
- Finally, return the modified list starting from
head, which is still the first node of the original list.
- Finally, return the modified list starting from
Solution in C++
C++
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
// Edge case: if the list is empty or contains only one node, return it as is
if (!head || !head->next) {
return head;
}
// Initialize two pointers for odd and even nodes
ListNode* odd = head; // Start with the first (odd) node
ListNode* even = head->next; // Start with the second (even) node
ListNode* evenHead = even; // We need to remember the head of even nodes
// Traverse the list and rearrange the nodes
while (even && even->next) {
odd->next = even->next; // Link the next odd node
odd = odd->next; // Move the odd pointer to the next odd node
even->next = odd->next; // Link the next even node
even = even->next; // Move the even pointer to the next even node
}
// After the loop, append the even list to the end of the odd list
odd->next = evenHead;
// Return the new head of the rearranged list
return head;
}
};Solution in Javascript
JavaScript
var oddEvenList = function(head) {
// If the list is empty or has only one node, no need to reorder
if (!head || !head.next) return head;
// Initialize pointers for odd and even lists
let odd = head; // Start of the odd-indexed list (the first node)
let even = head.next; // Start of the even-indexed list (the second node)
let evenHead = even; // Save the head of the even list so we can link the end of the odd list to it
// Traverse the linked list, rearranging nodes into odd and even positions
while (even && even.next) {
// Link the next odd node
odd.next = even.next;
odd = odd.next;
// Link the next even node
even.next = odd.next;
even = even.next;
}
// After rearranging, link the end of the odd list to the head of the even list
odd.next = evenHead;
// Return the modified head of the list
return head;
};Solution in Java
Java
class Solution {
public ListNode oddEvenList(ListNode head) {
// Edge case: If the list is empty or has only one node, return the list as is
if (head == null || head.next == null) {
return head;
}
// Initialize two pointers:
// odd points to the first node (head),
// even points to the second node (head.next)
ListNode odd = head;
ListNode even = head.next;
// We will also need to store the start of the even list to link it later.
ListNode evenHead = even;
// Traverse the list while there are nodes available in both odd and even positions
while (even != null && even.next != null) {
// Link the next odd node (which is even.next) to the current odd node
odd.next = even.next;
odd = odd.next; // Move the odd pointer to the next odd node
// Link the next even node (which is odd.next) to the current even node
even.next = odd.next;
even = even.next; // Move the even pointer to the next even node
}
// After the loop, the last odd node should point to the head of the even list
odd.next = evenHead;
// Return the reordered list, starting from the original head (first odd node)
return head;
}
}