理解python中的指標和合并串列-有解無憂

因此，我正在努力解決指標在 Python 中的作業/管理方式。具體來說，我正在研究一個練習問題，該問題接受兩個排序的整數鏈表（最小到最大），并回傳合并的排序鏈表。經過一個小時的頭撞墻后，我無法弄清楚該怎么做，所以我在網上找到了一個解決方案，特別是這個：

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1
            else:
                cur.next = list2
                list2, cur = list2.next, list2
                
        if list1 or list2:
            cur.next = list1 if list1 else list2
            
        return dummy.next

我理解主要思想：檢查當前節點的值，將較小的節點放入串列中，然后將該輸入串列向前移動一個節點，然后重復。但是，我正在努力解決curand dummy，以及它們在此解決方案中的作業方式：

為什么要dummy.next鏈接到cur？整個函式似乎只關心cur，并且沒有像 C 這樣的語言那樣將指標顯式移動dummy到頭部cur。我認為這與它們都被初始化的事實有關同一時間，但我不太明白怎么做？
為什么我們cur連續更新兩次？首先我們設定cur.next等于其中一個串列，然后我們cur在下一行設定自己等于同一個串列？我不明白為什么這是必要的，甚至不明白它在鏈表的構造中做了什么。

uj5u.com熱心網友回復：

每個 Python 變數都是對值的參考；如果您已經了解指標在 C 中是如何作業的，那么將參考可變物件的變數視為像 C 指標一樣作業可能會很有用。它們實際上并不是一回事，但是參考 a 的 Python 變數的ListNode行為更像是 CListNode*而不是 C ListNode，因此如果這是您來自的語言，那么指標隱喻是一個很好的概念起點。

dummy始終指向您在函式的第一行中創建的節點，該節點與cur開始的節點相同。第一次更新cur.next時，您也在更新dummy.next。 cur然后被重新分配給一個新節點，但您所做的修改dummy仍然存在。

這個 Python 代碼：

        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1

本質上是一樣的：

        ListNode* cur, dummy;
        cur = dummy = new ListNode();
        while (list1 && list2) {               
            if (list1->val < list2->val) {
                cur->next = list1;
                cur = list1;
                list1 = list1->next;
            }
        }

一是修改指向next的節點的屬性；cur另一個正在修改cur自身以指向新節點。

                cur.next = list2
                cur = cur.next

是相同的：

                cur->next = list2;
                cur = cur->next;

如需更深入地解釋變數在 Python 中的作業原理，請閱讀https://nedbatchelder.com/text/names.html

uj5u.com熱心網友回復：

為什么 dummy.next 鏈接到 cur？

它沒有。

最初，會創建一個額外的節點，以便源串列中的節點可以鏈接到它之后。dummy并且cur都是該節點的名稱，在函式的開頭。

隨著函式的進行，cur成為不同節點的名稱，但dummy仍然是最初創建的節點的名稱。

該函式回傳dummy.next，因為該函式通過在該節點之后按順序鏈接節點來作業，因此dummy.next參考（而不是“指向”）這些鏈接節點中的第一個。

并且沒有像 C 這樣的語言那樣將 dummy 的指標顯式移動到 cur 的頭部。

Python中沒有指標。進一步，cur是一個節點；它沒有“頭”。在這個實作中，沒有明確表示整個串列的物件——只有表示節點的物件，這樣串列就隱含地是某個節點以及從它可以到達的所有其他節點。

dummy開始是一個新創建節點的名稱。無需重新指定dummy為“串列頭”的名稱，因為它是該節點的名稱，從未停止作為該節點的名稱，并且該節點被用作串列的前任。（由于該節點實際上不是預期結果的一部分，因此我們必須在回傳時跳過它。）

為什么我們在連續的行中更新 cur 兩次？

首先，重要的是要了解我們不這樣做。詳細地：

首先我們設定 cur.next 等于其中一個串列，然后我們設定 cur 本身等于下一行中的同一個串列？

更改的值cur.next 與設定cur本身不同。例如，串列元素也會發生同樣的事情：

a = [1, 2, 3]
b = a
# changing an element of a WILL change what we see in b:
a[0] = 4
print(b)
# REPLACING `a` will NOT change what we see in b:
a = 'hi mom' # we don't even have to replace it with another list
print(b)

寫作b = a 不會復制串列。這意味著這b 是同一事物的另一個名稱a。如果我們改變那個東西，那么如果我們檢查，顯然我們會看到變化b。如果我們為a別的東西取名，那不會有影響b，因為b它仍然是以前的名字。

它與現實世界中人的實際名稱或其他形式的參考相同。鮑勃是愛麗絲最小的兒子。鮑勃長大后，愛麗絲觀察到“我最小的兒子”長大，因為這意味著同一個人。如果愛麗絲生了另一個男孩，并擁抱“我最小的兒子”，鮑勃不會感覺到擁抱——因為“我最小的兒子”不再意味著同一個人。

我不明白為什么這是必要的

現在我們可以考慮代碼的用途。

cur是我們用于“我們正在構建的串列的當前最后一個節點”的名稱。

由于我們將節點添加到串列中以構建它，因此隨著時間的推移，它必須參考不同的節點。

通過這樣做cur.next = ...，我們在被命名的節點之后鏈接另一個節點cur。這有助于我們構建串列，但現在cur不再是最后一個節點的名稱 - 因為它仍然是它之前命名的節點的名稱，并且該節點不再是最后一個節點，因為我們添加了一個節點。

所以，在添加完節點之后，我們重新分配cur給剛剛添加的節點命名。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/470461.html

標籤：Python 指针链表

上一篇：如何檢測一塊記憶體是否已經釋放

下一篇：為什么指標的資料型別應該與它所尋址的變數的資料型別相同？[復制]