首先我理解这样的写法并非最佳实践,只是想理解语言差异与背后的原因。
这是一道 LeetCode 题,讨论区里面每种语言都用了相同的解法,但只有 Python 以同样的写法陷入了死循环,问了 AI 都说两种写法等价,所以不应该存在 bug ,但实测显然是不同的,所以想问问原因。
注意看 while 循环里为两个指针连续赋值的地方。
C++ 版:
ListNode *partition(ListNode *head, int x) {
ListNode node1(0), node2(0);
ListNode *p1 = &node1, *p2 = &node2;
while (head) {
if (head->val < x)
p1 = p1->next = head;
else
p2 = p2->next = head;
head = head->next;
}
p2->next = NULL;
p1->next = node2.next;
return node1.next;
}
Java 版:
public ListNode partition(ListNode head, int x) {
ListNode smallerHead = new ListNode(0), biggerHead = new ListNode(0);
ListNode smaller = smallerHead, bigger = biggerHead;
while (head != null) {
if (head.val < x) {
smaller = smaller.next = head;
} else {
bigger = bigger.next = head;
}
head = head.next;
}
// no need for extra check because of fake heads
smaller.next = biggerHead.next; // join bigger after smaller
bigger.next = null; // cut off anything after bigger
return smallerHead.next;
}
我自己翻译的 Python 版,然而死循环导致超时:
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
lt, ge = ListNode(), ListNode()
ltPtr, gePtr = lt, ge
while head:
if head.val < x:
ltPtr = ltPtr.next = head
else:
gePtr = gePtr.next = head
head = head.next
ltPtr.next, gePtr.next = ge.next, None
return lt.next
翻了一下讨论区,下面的是没问题的 Python 版:
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
head1 = tail1 = ListNode()
head2 = tail2 = ListNode()
while head:
if head.val < x:
tail1.next = tail1 = head
else:
tail2.next = tail2 = head
head = head.next
tail2.next = None
tail1.next = head2.next
return head1.next
问题就出在了为两个指针连续赋值的地方,所以为什么在 Python 中,p = p.next = q 与 p.next = p = q 是不等价的呢?分别都是怎样的步骤进行赋值的?
|