关于链表题dummy head的问题。

一般我们setup 一个dummy node。 dummy.next = head. 然后做一些操作。最后return dummy.next。
比如这一题。 https://leetcode.com/problems/insertion-sort-list/
答案 https://leetcode.com/problems/in ... -clear-way-to-sort-(-O(1)-space-)

我的问题是，为什么 helper.next是新链表的头？ helper是跟着pre改变，比如4-2-1. pre最后会指向1，helper也跟着指向1. 但是4-2-1-3， pre最后会指向3，为什么helper还能指向1？？？

链表有好多这样的例子，我一直没弄明白。望指教。

一家之言:
需要创建dummyHead的一般有两个情况:
1. head节点有可能被删除，或者新创建。比如去重的题目，如果发现重复就要全部去除；比如新创建链表的时候(奇偶链表那道)。
2. head作为cursor需要指导后面的操作的时候。这种情况也可能可以通过创建新的cursor指针得到解决。
简而言之，就是头结点不确定的时候，往往需要dummyHead节点。

使用prev作为cursor(指的是对prev.next节点进行操作)，相比较cur作为cursor(指的是对current节点进行操作)，会有更多的灵活性，因为可以直接删除。

ftr好好学习 发表于 2020-9-7 07:03
这里的pre是dummy的一份copy啊，只是初始和dummy指向一个地址，但两者是独立的。看C++那种有指针的语言写出 ...

正解。举个简单的例子

1. cur = head;
   
2. prev = cur;
   
3. cur = cur.next;

复制代码

这段运行以后pre会指向head， 而cur指向head.next。prev = cur只是把cur在那个状态下的reference复制给pre，以后cur怎么变并不会影响pre。

答案链接打不开， 截了个图在这里。

这里的pre是dummy的一份copy啊，只是初始和dummy指向一个地址，但两者是独立的。看C++那种有指针的语言写出来的链表代码，可以帮助理解

ftr好好学习 发表于 2020-9-7 07:03
这里的pre是dummy的一份copy啊，只是初始和dummy指向一个地址，但两者是独立的。看C++那种有指针的语言写出 ...

独立的话，最后return的dummy.next为什么能指向最新的node？ 在dummy被定义以后，没有任何code去update dummy.next.

这是C++版本，明显dummy.next指向了head。上面Java版本确没有

helper和pre最开始是一样的，然后pre指向某个新的head，helper也同时指向那个head了，然后pre变了，变成pre=pre.next,这个时候helper并没有变，也就是pre和helper这时候不指向相同节点了，pre无法改变helper了。也就是pre往后遍历了，helper还是指向那个head。循环的最后，pre=helper，相当于pre又重置到了helper，这时候pre又和helper一样了，也就是pre改变helper也会改变，那么新的循环中pre下一次变化又会使helper指向新的head，但是仅此而已，helper没有往后遍历，只是helper指向的节点变了，自己没变，也就是helper永远指向每次循环中的head。但是pre =pre.next之后，pre就和helper不一样了，这时pre的改变就不会改变helper。所以helper实际就是每次循环pre=helper的时候 pre的改变会改变helper的next，pre=pre.next之后helper就和pre没关系了，所以helper可以永远指向最新的head。结论：pre=helper的时候，pre会改变helper，但是pre=pre.next之后，pre就不会改变helper了；而helper一直没变，只是每次循环被动的被pre改变了next。

楼上都很好

变量被重新赋值了 所以pre不再是原来的dummy那个node