Leetcode成对交换节点(Python)

Question

我正试图解决leetcode问题24:成对交换节点。问题描述如下:

给定一个链表，交换每两个相邻节点并返回其头部。你必须在不修改列表节点值的情况下解决这个问题(也就是说，只有节点本身可以被改变)

示例1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]

我的代码如下:

class Solution(object):
def swapPairs(self, head):
if not head or not head.next:
return head

curr = head    
curr_adj = curr.next 
while curr and curr.next:

# Saving the next Pair
next_pair = curr.next.next # Here im saving the next pair (i.e., the value 3)
# Swaping the nodes
curr_adj.next = curr   # pointing 2 --> 1
curr.next = next_pair  # pointing 1 --> 3
# so I assume I would have 2-->1-->3-->4
# update the ptrs 
curr = next_pair       # now curr should be 3
curr_adj = curr.next   # curr_adj should be 4

return head
# at the next iteration, I assume 4 --> 3 --> Null 
# So finally, I should have 2-->1-->4-->1--> Null

我得到以下错误。我做错了什么?

AttributeError: 'NoneType' object has no attribute 'next'
curr_adj = curr.next

Answer 1

注意这一行:

next_pair = curr.next.next

从您的循环条件来看，curr.next.next有可能是None。结果为next_pair = None。

然后，分配curr = next_pair。当试图访问不存在的curr、curr_adj = curr.next的next属性时，出现错误。

为什么不考虑递归方法呢?

class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
n1, n2 = head, head.next
n1.next, n2.next = self.swapPairs(n2.next), n1
return n2