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.
Example 1:
Input:1->2->3->4->5->NULLOutput:1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULLOutput:2->3->6->7->1->5->4->NULL
Constraints:
[0, 10^4].
The description was taken from https://leetcode.com/problems/odd-even-linked-list/.
# O(N) Time, O(1) Spaceclass Solution: def oddEvenList(self, head: ListNode) -> ListNode: if not head: return head odd, even = head, head.next even_head = even while even and even.next: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = even_head return headWe can solve this problem by reordering the pointers to create two sublists. One sublist will contain all of the odd ordered nodes, the other will contain all of the even ordered nodes.
We can then connect the two sublists and return the reordered linked list.
Since we aren't creating any new nodes and are just reordering the pointers, we won't be allocating any significant amount of memory. This algorithm will run in linear time and constant space.
We will start off by checking if the linked list we have been given is none.
If it is, we will return none, because we won't have any even or odd nodes.
if not head: return head
The description states that the first node is considered odd and the second is considered even, we aren't actually basing their order in the list off of the values.
Below is an example input list with the odd nodes highlighted in green and the even nodes highlighted in red.
2->1->3->5->6->4->7->None
We see that the head of the list, node one, is odd, and the next node, node two, is even.
We will initialize our odd and even pointers at these two nodes.
odd, even = head, head.next
The first even node will be the head of the even list, so we will make note of that so we can connect the odd sublist tail to it later.
even_head = even
We will then create a loop that will run while the even pointer isn't at a null node and the next node also isn't null also.
The reason why we want to do this is that if there is an even number of nodes in the linked list, we would make the tail of the odd list a null node.
2->1->3->5->6->4->7->None
If we then try to connect that null node to the head of the even list later, we will get an error. That is why we need to exit the loop right when we see that the node coming up is null. We will have already stepped to the eight-valued node in the previous iteration, so we don't need to worry about missing the last even value in our even sublist.
while even and even.next:
While inside of our loop, we will move two nodes at a time to the odd and even sublists.
This is done by moving each node's next pointers to other nodes of the same order.
2->1->3->5->6->4->7->None
As we can see above, we will want to write that the node that should come next to the current odd node is the odd node that is currently next to the even node.
odd.next = even.next
After we have put these two odd nodes next to each other, we will want to step the next odd node so that we can continue moving down the list to do the same thing.
odd = odd.next
The same thing will be done for the even nodes.
even.next = odd.next even = even.next
Once we have created the two sublists, we will just need to set the last node of the odd sublist's next value to the head of the even list and return the reordered list.
odd.next = even_head return head