Question

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. What should be the implementation of the program to achieve this?

Answer 1

To group odd and even nodes of a singly linked list together, we can use two pointers and iterate through the list, moving the odd nodes to one side and the even nodes to the other side. The implementation uses O(1) space complexity and O(nodes) time complexity.

Step-by-step explanation:

To group the odd and even nodes of a singly linked list together in place, we can use two pointers. One pointer, odd_ptr, will keep track of the odd nodes, and another pointer, even_ptr, will keep track of the even nodes. We also need to keep a reference to the first even node to connect it with the last odd node later.

We can iterate through the list, moving the odd nodes to one side and the even nodes to the other side, connecting them at the end. Here is the implementation:

ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* odd_ptr = head;
ListNode* even_ptr = head->next;
ListNode* even_head = even_ptr;
while (even_ptr && even_ptr->next) {
odd_ptr->next = even_ptr->next;
odd_ptr = odd_ptr->next;
even_ptr->next = odd_ptr->next;
even_ptr = even_ptr->next;
}
odd_ptr->next = even_head;
return head;
}