Re: [问题] 新手解LeetCode:Swap Nodes in Pairs

楼主: s06yji3 (阿南)   2016-08-03 20:34:45
简单讲一下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 <
楼主: s06yji3 (阿南)   2016-08-03 20:39:00
打返啦......tmp=tmp.next才对
作者: Sunal (SSSSSSSSSSSSSSSSSSSSSSS)   2016-08-03 21:05:00
楼上是说这一行吧 “例如,tmp = head; tmp.next = tmp”
楼主: s06yji3 (阿南)   2016-08-03 21:10:00
是的QQ,现在用手机不知道怎么修改
作者: iwantstronge (...)   2016-08-04 08:30:00
非常感谢您如此清晰具体的讲解!! 我后来是理解为因为等号有传址的意位,所以在对调后造成tmp.next.next又连结回tmp的开头,也就是这篇说的失去跟node3,4的连结~只是我有点好奇高手们在解这类题目时也是一步步把炼表写出来思考吗? 不然这题如果改成一次变动多个元素的话,感觉会画到崩溃...
楼主: s06yji3 (阿南)   2016-08-04 12:01:00
写多了就习惯了吧@@

Links booklink

Contact Us: admin [ a t ] ucptt.com