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

[s06yji3 (阿南)]

簡單講一下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: 打返啦......tmp=tmp.next才對
推 Sunal: 樓上是說這一行吧 「例如，tmp = head; tmp.next = tmp」
→ s06yji3: 是的QQ，現在用手機不知道怎麼修改
推 iwantstronge: 非常感謝您如此清晰具體的講解!!  我後來是理解為因
→ iwantstronge: 為等號有傳址的意位，所以在對調後造成tmp.next.nex
→ iwantstronge: t又連結回tmp的開頭，也就是這篇說的失去跟node3,4
→ iwantstronge:  的連結~
推 iwantstronge: 只是我有點好奇高手們在解這類題目時也是一步步把
→ iwantstronge: 鍊表寫出來思考嗎？ 不然這題如果改成一次變動多個
→ iwantstronge: 元素的話，感覺會畫到崩潰...
→ s06yji3: 寫多了就習慣了吧@@