I'm trying to solve Leetcode Q328:
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.
Here is my code:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node = head
odd = True
lastOdd = None
while node:
temp = node.next
if node.next:
if node.next.next:
node.next = node.next.next
else:
if odd:
lastOdd = node
else:
if odd:
lastOdd = node
break
node = temp
odd = not(odd)
lastOdd.next = head.next
return head
When tested with [1,2,3,4,5], I would either run out of time or memory, so I'm assuming there is a deadloop somewhere. But I've combed through the logic a couple of times and couldn't find it!
I'm relatively sure that the deadloop happens with the following part as deleting this part will allow the program to finish:
else:
if odd:
lastOdd = node
This is actually already the second version of my code, originally it was:
else:
if odd:
node.next = head.next
But why does it deadloop? I have used temp to store the next node in the original chain separately already, and the loop should just stop after node reaches the end of the chain!
Any help is appreciated! I'm just starting to learn about linked lists so it might be a really dumb question.
Your analysis is correct that the issue lies in the logic for updating pointers, which can inadvertently create a cycle in the linked list.
The root cause of the deadloop is this line:
lastOdd.next = head.next
In your code, lastOdd is the last node in the odd-indexed group. At the end of the traversal, you're connecting this node's next to head.next, which is the head of the even-indexed group.
If the head.next pointer (i.e., the even list) still points somewhere in the odd-indexed list, you create a cycle. This happens because you never "terminate" the even list properly with a None value.
Eg:
Consider the input [1, 2, 3, 4, 5]:
The odd-indexed group should be [1, 3, 5]. The even-indexed group should be [2, 4]. You need to link the next pointer of 5 (last odd) to the head of the even list (2), while ensuring that the next of the last even node (4) is None.
However, in your code, the even list's next pointers are not handled properly. If 4's next still points to 5, you create a cycle.
Corrected code:
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
odd = head
even = head.next
even_head = even # Store the head of the even-indexed list
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
# Connect the last odd node to the head of the even list
odd.next = even_head
return head