交换链表中的节点时发生TLE错误

Question

我正在尝试在leetcode上"成对交换节点"(https://leetcode.com/problems/swap-nodes-in-pairs/)。

我的代码在下面。它只为一个测试用例生成TLE错误。我真的不确定它是否陷入了无限循环。感谢您的帮助。

def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
ans=h=ListNode(0)
while head and head.next:
h.next=head.next
h.next.next=head
h=h.next.next
head=head.next.next
h.next=head
return ans.next

Answer 1

我在您的代码中看到的问题是这里的这一行h.next.next=head。我假设您正在尝试设置相邻节点，但这实际上是在第一次运行时将整个列表设置为h.next.next。反过来，在这里再次设置head=head.next.next，这只会导致您怀疑的无限递归。

既然你已经掌握了关键点，我希望你能纠正错误并实施你的解决方案。

我已经重新实施了您的以下解决方案。

class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or head.next == None:
return head
first = cur = ListNode(0) #initialize a node object with 0 value
cur.next = head #get accesss to the first node
while (cur.next and cur.next.next):
a = cur.next
b = cur.next.next
c = cur.next.next.next
#swap the nodes here
cur.next = b
cur.next.next = a
cur.next.next.next = c
cur = cur.next.next # sets it to one before the next node
return first.next