首页 > 代码库 > 链表：二级指针的使用
链表：二级指针的使用
博文的记录源自阅读著名的酷壳主页：http://coolshell.cn/articles/8990.html
Coolshell图文并茂说明了这个问题——我们在删除链表的时候，常常需要记录该结点在链表中是否有前趋prev。如果有，那么需要把prev->next指向该结点的next域，然后再删除该结点，这样才能保证链表不会因为删除结点而“断开”。像这样：
void remove(list_node **ref_head, list_node *del){ if ((*ref_head) == NULL || del == NULL) return; list_node *cur = *ref_head, *prev = NULL; while (cur) { if (cur == del) { if (prev) { prev->next = cur->next; } else { *ref_head = cur->next; } delete cur; cur = NULL; break; } prev = cur; cur = cur->next; }}
那么，在遍历链表的时候，这种方法需要对prev is null or not进行判断，这在Linus Torvalds看来，是不聪明的做法，是不理解指针的表现。稍微想一下就知道，其实这样做的根本原因也很明了，第一，需要知道被删除的结点是否是链表的头结点，第二，需要保证链表在删除后不会“断开”。
Linus的做法是用一个二级指针，去引用prev的next域。假设链表的结构名为list_node，那么这时要记录的不是list_node *prev，而是list_node **ref_prev。首先，实现代码是这样的：
void remove(list_node **ref_head, list_node *del) { if ((*ref_head) == NULL || del == NULL) return; list_node *cur = *ref_head, **ref_prev = ref_head; while (cur) { if (cur == del) { *ref_prev = cur->next; delete cur; cur = NULL; break; } ref_prev = &(cur->next); cur = cur->next; }}
由代码可以看出，在执行cur = cur->next之前，首先用一个二级指针去引用当前cur的next域，其实也就是引用了方法一中的prev->next，这个原理和函数中的“传值”是一致的，就像swap函数一样，如果函数原型如void swap(int a, int b)，即pass-by-value，这时函数执行时的变量a,b只是传入参数的一个副本，函数执行完毕对传入的变量值没有影响，要让值改变，函数应该是传入地址void swap(int &a, int &b)；**ref_prev的道理也是如此，它不是记录prev，而是引用了prev的next域，在必要的时候改变prev->next的指向，这保证了链表不“断开”。其次，ref_prev的初始指向为链表的头结点，如果删除的结点是头结点，*ref_prev = cur->next也只是简单地把头结点改为原先头结点的next结点，不需要再判断prev是否为NULL了。
今天看到了一道题目，大体意思是链表是排好序的，要你插入一个结点后，仍保持排序。稍微想想，似乎也是需要记录prev，如果插入的结点在链表内（非头结点也非尾结点），则要有这样的操作：prev->next = new_node; new_node->next = cur; （这里假定prev->value <= new_node->value <= cur->value, 即链表是升序排序的）很明显，这里的操作也可以用二级指针。
void insert_to_sorted_list(list_node **ref_head, int value, bool (*func)(int, int)) { if ((*ref_head) == NULL) return; list_node **ref_next = ref_head; list_node *cur = *ref_head; list_node *new_node = new list_node; new_node->value =http://www.mamicode.com/ value; new_node->next = NULL; while (cur) { if (func(value, cur->value)) { new_node->next = cur; *ref_next = new_node; return; } ref_next = &(cur->next); cur = cur->next; } *ref_next = new_node;}
这里考虑到题目未说明链表的排序方式（升序／降序），函数原型在参数里加入了一个函数指针。如果是在面试，这应该是个“考虑周全”的加分点吧？
链表：二级指针的使用