Fun problem, pretty intuitive solution. We’re given a singly linked list and asked to relink and return it with a catch - all odd-indexed nodes should be linked together in a group, and all even-indexed nodes should be linked together in a group succeeding the odd-indexed node group.
The best way to solve this is with a whiteboard, but afterwards we quickly identify the edge cases. We just need to make sure that for smaller lists we don’t run into referencing non-existant nodes. Maintain an even and an odd pointer that we use to traverse and link odd and even nodes together. We also need a third node to maintain the location of the even list’s head.
After successfully linking together the odd and even nodes, we link the odd list to the even list using the third pointer mentioned ealier. We then return the head of the list.
The solution is as follows:
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
odd = head
even = conn = head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = conn
return head_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We maintain pointers in constant space.