我在用C++写 Leetcode中 Remove duplicates from linked list II 一题时,看到别人的一份代码,感觉写法很有趣,细细研究了一下。受益不少。

在大部分链表题中,我们习惯于创建一个空节点dummy,使之指向链表的头结点,以方便对
第一个节点进行操作(比如,删除它)。最后答案返回dummy.next。比较有节操的同学会在
删除链表的某些节点时用delete,以免内存泄露,但是难道就没有考虑过dummy节点感受么?

使用一个二维指针,可以优雅的解决了这个问题。

举个简单的🌰:

1
2
3
4
5
6
7
8
9
10
/*
* Suppose we have a linked list "1->2->3", we want to delete the
* second node, remains "1->3".
*/

ListNode **p = &head, *succ;
p = &(*p)->next;
succ = (*p)->next;
delete (*p);
(*p) = succ;

尝试解释一下下。p是一个二级指针,也就是说,在一开始,p是一个指向一个指向head指针的指针(也就是(*p)指向head)。这样的好处就是,当我们需要在某一个时刻删除指向的节点(delete *p操作),p本身不受影响(当然,是p指向的指针所对应的内存空间被释放了)。唯一一点不方便的时,其他每次移动的时候,都要用(*p)(p淡淡的看着他指向的指针往后移。)

和用dummy解法不同的是,dummy解法指针后移是ptr = ptr->next;。那我们这呢?(*p) = (*p)->next;?这样是错的。比如1->2里从1移动到2的过程中,就把节点1修改了。所以,要移动的是p。即为p = &(*p)->next,其中->的优先级是高于&的,把p赋值为(*p)->的地址,所以现在(*p)指向老(*p)的next。

另一个大家可能关心的问题,在delete (*p)后,(*p)的前驱节点的next是怎么不找丢的呀?这其实涉及到delete的本质(Stackoverflow对这个问题有个不错的回答)。当我们调用delete的时候,那块内存里的数据其实并没有消失,只是这块内存地址被标记为可以利用,当之后的程序需要new的时候,才有可能覆盖掉这里的数据。就像爱情,没有一段新的覆盖,老的怎么忘的掉(情人节了还在改博客,唉~~)。所以这个代码严格意义上说是由风险的,如果在delete的一瞬间,正好另一个程序/进程new了一块内存,又刚好是这里,这个方法就废了。fix的方法就是delete前,赋给一个临时变量,把next覆盖当前,再delete临时变量。

修改的过程中,发现陈皓也写过类似的文章,这个trick被Linus举例为什么才是core low-level coding,真正懂指针的做法。 他的文章还有配图,如果我表述的还是没让大家理解,推荐去读一下。

PS:《Pointers In C》的第十二章《Using Structures and Pointers》,也有关于指针链表操作的详细解释。