Re: [問題] 新手解LeetCode:Swap Nodes in Pairs

看板Python作者s06yji3 (阿南)時間7年前 (2016/08/03 20:34)推噓3(3推 0噓 8→)

留言11則, 3人參與討論串2/2 (看更多)

簡單講一下list node，如果你已經知道的話可以跳過。直接看你對調code之後listed node的變化。 listed node的操作只是改變node之間的指向或是node的值。所以兩個以上的指標在操作listed node的時候，要注意現在的每個參照名稱的所在位置，還有這個操作對所以有node有什麼影響。 node的定義： class node(object): def __init__(self, val): self.val = val self.next = None *為參照名稱所在的位置例如，head = 1*->2->3->4，則透過head可以操作node 1的指向或更改node 1的值。要跳到node 2就可以用head = head.next 在這種情況，你就失去1的參照，所以怎樣也回不去node 1。在不考慮garbage collection的情況下node 1依然指向node 2 如果在移動head前，tmp = head (=1*->2->3->4) head移動之後，你依然可以利用tmp去連結node 1 順道一題，要刪除listed node中的一個node就是讓這個node失去和所有參照名稱連結。例如，head.next = head.next.next 這個情況下head = 1*->3->4，其實也只是將node 1直接指向node 3。若沒有其他名稱參照的設定的話，就永久失去連結node 2的方法。不過你可以實驗在用head刪除node 2前，將一個名稱綁在node 2。例如，tmp = head; tmp.next = tmp 在用head刪除node 2之後，tmp.val是2 tmp.next.val是3 ======================================================== *:該名稱所在位置進入迴圈前： head = 1*->2->3->4 dummy = 0*->1->2->3->4 # dummy = node(0); dummy.next = head pre = 0*->1->2->3->4 # pre = dummy tmp = 1*->2->3->4 # tmp = head 以下()內的數字為whie之下第幾行執行過後原本： (1):pre.next = tmp.next head = 1*->2->3->4 dummy = 0*->2->3->4 pre = 0*->2->3->4 tmp = 1*->2->3->4 (2):tmp.next = tmp.next.next head = 1*->3->4 dummy = 0*->2->3->4 pre = 0*->2->3->4 tmp = 1*->3->4 (3):pre.next.next = tmp head = 1*->3->4 dummy = 0*->2->1->3->4 pre = 0*->2->1->3->4 tmp = 0->2->1*->3->4 (4):pre = tmp head = 1*->3->4 dummy = 0*->2->1->3->4 pre = 0->2->1*->3->4 tmp = 0->2->1*->3->4 (5):tmp = tmp.next head = 1*->3->4 dummy = 0*->2->1->3->4 pre = 0->2->1*->3->4 tmp = 0->2->1->3*->4 對調後： (1):pre.next = tmp.next head = 1*->2->3->4 dummy = 0*->2->3->4 pre = 0*->2->3->4 tmp = 1*->2->3->4 (2):pre.next.next = tmp 用pre講2指向1，但tmp還在1的位置且1指向2，失去3跟4的連結 head = 1*->2->1->2->1->2->... dummy = 0*->2->1->2->1->2->... pre = 0*->2->1->2->1->2->... tmp = 1*->2->1->2->1->2->... (3):tmp.next = tmp.next.next 1自己指向自己 head = 1*->1->1->1->1->1->... dummy = 0*->2->1->1->1->1->... pre = 0*->2->1->1->1->1->... tmp = 1*->1->1->1->1->1->... (4) head = 1*->1->1->1->1->1->... dummy = 0*->2->1->1->1->1->... pre = 1*->1->1->1->1->1->... tmp = 1*->1->1->1->1->1->... ※ 引述《iwantstronge (...)》之銘言： : 最近開始用Python解題 : 未學過正規的Python 因此對於一些觀念尚不太了解 : 題目是將鏈表中的元素兩兩對調 : 例如: Given 1->2->3->4, return the list as 2->1->4->3 : 我的Code如下: : class Solution(object): : def swapPairs(self, head): : if head is None or head.next is None: : return head : dummy = ListNode(0) : dummy.next = head : pre = dummy : tmp = head : while tmp and tmp.next: : pre.next = tmp.next : tmp.next = tmp.next.next <---有疑問 : pre.next.next = tmp <---有疑問 : pre = tmp : tmp = tmp.next : return dummy.next : 以上的Code沒問題 : 但如果我將上面標示有疑問的那兩行順序對調，改成: : class Solution(object): : def swapPairs(self, head): : if head is None or head.next is None: : return head : dummy = ListNode(0) : dummy.next = head : pre = dummy : tmp = head : while tmp and tmp.next: : pre.next = tmp.next : pre.next.next = tmp <---已對調 : tmp.next = tmp.next.next <---已對調 : pre = tmp : tmp = tmp.next : return dummy.next : 系統將會出現Time Limit的錯誤 : 就我的認知，這兩行對調應該完全沒差別？ : 另一個問題是，我在一開始將dummy指定給pre 掃描鏈表時是用pre在跑 : 而最後直接return dummy時，dummy也會跟著pre的變化而改變? 代表那個'等號'的operator : 是有傳址的意味在,而不像一般的等號直接複製到另一塊新的記憶體? : 以上問題，還請高手們提點，感激不盡！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.24.0.163 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1470227688.A.F70.html

→

s06yji3

08/03 20:39, , 1^F

08/03 20:39, 1^F

推

Sunal

08/03 21:05, , 2^F

08/03 21:05, 2^F

→

s06yji3

08/03 21:10, , 3^F

08/03 21:10, 3^F