我正在处理链表中k个节点的问题反转组。当我写分配操作来进行反转时，我给出了：
cur, cur.next, prev = cur.next, prev, cur
其中CCD_ 1和CCD_。发生的最有趣的事情是，当我给出：
cur.next, cur, prev = prev, cur.next, cur
它被接受，而前者给我的时间限制超过了。
我相信在Python中，多个变量的赋值将这些变量作为元组，并且只考虑所有变量的先前值。那么这两种说法应该完全一样，对吧？还是我错了？请帮帮我。
这是一个leetcode问题，我提供了整个代码以备不时之需。这一行用3*标记，如果我单独更改这一行，代码将从接受跳到超过时间限制。
h=jump=ListNode(0)
h.next=left=right=head
while True:
i=0
while i<k and right:
i+=1
right=right.next
if i==k:
prev=right
cur=left
for _ in range(k):
***cur.next, cur, prev = prev, cur.next, cur***
jump.next,jump,left=prev,left,right
else:
return h.next
接受上述代码。只有当我改变线路时，它才有点陷入一个循环，超过了时间限制。
分配是从左到右的，所以…
cur, cur.next, ... = ...
以上内容首先分配给cur。然后到cur.next，其中cur已经是新值。
cur.next, cur, ... = ...
这首先分配给cur.next，其中cur仍然是旧值。然后到CCD_ 8。
所以这就是你的不同。您可以更改不同节点的.next。
非常好的问题
现在我也明白了这个问题！(？_？(
这是链表中一个非常常见的问题，在遍历链表或执行任何其他操作时，我们应该始终注意语句中的更改顺序。
问题是，如果我们的报表中的一些所需订单会被遗漏(这里的情况就是这样(，最终会出现以下两种情况之一：
- 一个节点将错过到下一个节点的链接，如果你愿意的话，该节点将变得无链接
- 或者一个节点会链接回自己(就像一个圆圈(，列表就会过时
如果没有超过时间限制(刚刚测试(，具有正确顺序的代码将完全正常工作：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
h = jump = ListNode(0)
h.next = left = right = head
while True:
i = 0
while i < k and right:
i += 1
right = right.next
if i == k:
prev = right
cur = left
for _ in range(k):
cur.next, cur, prev = prev, cur.next, cur
jump.next, jump, left = prev, left, right
else:
return h.next
我们还可以使用助手函数。这将在没有超过时间限制(TLE(的情况下通过：
class Solution:
def reverseKGroup(self, head, k):
def rev(head, count):
prev, curr, next = None, head, head
while count > 0:
next = curr.next
curr.next = prev
prev, curr, count = curr, next, count - 1
return (curr, prev)
count, curr = 0, head
while curr and count < k:
curr, count = curr.next, count + 1
if count < k:
return head
new_head, prev = rev(head, count)
head.next = self.reverseKGroup(new_head, k)
return prev
以下是LeetCode的官方解决方案，并附有解释性注释：
递归
class Solution:
def reverseLinkedList(self, head, k):
# Reverse k nodes of the given linked list.
# This function assumes that the list contains
# atleast k nodes.
new_head, ptr = None, head
while k:
# Keep track of the next node to process in the
# original list
next_node = ptr.next
# Insert the node pointed to by "ptr"
# at the beginning of the reversed list
ptr.next = new_head
new_head = ptr
# Move on to the next node
ptr = next_node
# Decrement the count of nodes to be reversed by 1
k -= 1
# Return the head of the reversed list
return new_head
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
count = 0
ptr = head
# First, see if there are atleast k nodes
# left in the linked list.
while count < k and ptr:
ptr = ptr.next
count += 1
# If we have k nodes, then we reverse them
if count == k:
# Reverse the first k nodes of the list and
# get the reversed list's head.
reversedHead = self.reverseLinkedList(head, k)
# Now recurse on the remaining linked list. Since
# our recursion returns the head of the overall processed
# list, we use that and the "original" head of the "k" nodes
# to re-wire the connections.
head.next = self.reverseKGroup(ptr, k)
return reversedHead
return head
迭代
class Solution:
def reverseLinkedList(self, head, k):
# Reverse k nodes of the given linked list.
# This function assumes that the list contains
# atleast k nodes.
new_head, ptr = None, head
while k:
# Keep track of the next node to process in the
# original list
next_node = ptr.next
# Insert the node pointed to by "ptr"
# at the beginning of the reversed list
ptr.next = new_head
new_head = ptr
# Move on to the next node
ptr = next_node
# Decrement the count of nodes to be reversed by 1
k -= 1
# Return the head of the reversed list
return new_head
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
ptr = head
ktail = None
# Head of the final, moified linked list
new_head = None
# Keep going until there are nodes in the list
while ptr:
count = 0
# Start counting nodes from the head
ptr = head
# Find the head of the next k nodes
while count < k and ptr:
ptr = ptr.next
count += 1
# If we counted k nodes, reverse them
if count == k:
# Reverse k nodes and get the new head
revHead = self.reverseLinkedList(head, k)
# new_head is the head of the final linked list
if not new_head:
new_head = revHead
# ktail is the tail of the previous block of
# reversed k nodes
if ktail:
ktail.next = revHead
ktail = head
head = ptr
# attach the final, possibly un-reversed portion
if ktail:
ktail.next = head
return new_head if new_head else head
参考文献
- 有关更多详细信息，请参阅讨论板，在那里您可以找到大量解释良好的公认解决方案，这些解决方案使用各种语言，包括低复杂度算法和渐近运行时/内存分析1，2