最近正在重读《编程珠玑》，对于以前忽略的细节，现在也有了更深的了解。
这是13章课后习题中的第4题，向有序单链表中插入新结点。linus曾经谈到过使用二级指针删除结点的问题，具体请见“酷壳网”。

作者介绍了两种方法，并在链表中创建了哨兵结点，第一种是我们常用的一级指针，我将它改成了C语言版本（其实没改什么东西），如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void insert(int t)
{
    node * p;

    if(head->val == t)
        return ;

    if(head->val > t)
    {
        head = newNode(t ,head);
        return ;
    }

    for(p = head; p->next->val < t; p = p->next)
    ;

    if(p->next->val == t)
        return ;

    p->next = newNode(t, p->next);
}

这是我们常用的方法，也是老师讲过的标准方法，需要对head结点单独进行讨论，这个方法不难理解。
下面我们主要讨论作者介绍的第二种方法，使用二级指针来插入新结点，代码如下： 

1
2
3
4
5
6
7
8
9
10
11
/* 使用二级指针操作 */
void insert(int t)
{
    node **p;

    for(p = &head; (*p)->val < t; p = &((*p)->next))
    ;
    if ((*p)->val == t)
        return;
    *p = newNode(t, *p);
}

使用二级指针就可以不用将头结点单独讨论，插入第一个结点时， p = &head，*p = newNode(t, *p)，相当于第一中方法中的 head = newNode(t ,head), 这样第二种方法就将第一种方法中的两种情况(头结点和非头结点)都包含了。
对于非头结点的情况，即当前结点有前驱结点(设为prev结点)，此时*p 的值等于prev->next，即 *p = newNode(t, *p) 相当于 prev->next = newNode(t, prev->next)。
为了加深理解，我用gdb追踪各指针。 初始化链表后，head和sentinel都指向哨兵结点。

当我们使用二级指针向链表中插入1时：
insert函数的for循环结束后：

此时p指针指向的是head指针，p等于head。 执行完 p = newNode(t, p); 之后：

此时p指针仍然指向head指针，但是head指针的指向了新插入的结点。 向链表中插入2，执行完insert函数中的for循环：

将存储1的结点命名为prev，0x602038其实是prev-next的地址，即此时p存储的是prev->next的地址，p指向的是哨兵结点。 执行 p = newNode(t, p); 相当于执行 prev->next = newNode(t, prev->next)。 执行完之后:

此时p仍然指向prev->next,但是prev的next保存的地址变成了新生成的结点的内存地址，这样就完成了新结点的插入。
下面附上完整代码，方便需要的人运行，调试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int val;
struct node *next;
}node;

node *head, *sentinel;

node* newNode(int val, node *n)
{
node *temp = (node*)malloc(sizeof(node));
temp->val = val;
temp->next = n;

return temp;
}

void initList(int maxval)
{
sentinel = head = newNode(maxval, 0);
}
/* 使用二级指针操作 */
void insert(int t)
{
node **p;

for(p = &head; (*p)->val < t; p = &((*p)->next))
;
if ((*p)->val == t)
return;
*p = newNode(t, *p);
}
/* 一级指针 */
/* void insert(int t) */
/* { */
/* 	node * p; */

/* 	if(head->val == t) */
/* 		return ; */

/* 	if(head->val > t) */
/* 	{ */
/* 		head = newNode(t ,head); */
/* 		return ; */
/* 	} */

/* 	for(p = head; p->next->val < t; p = p->next) */
/* 		; */

/* 	if(p->next->val == t) */
/* 		return ; */

/* 	p->next = newNode(t, p->next); */
/* } */

int main(int argc, char *argv[])
{
initList(50);

int a[5] = {1, 2};

int i;
for (i = 0; i < 2; ++i)
insert(a[i]);

node *iterator;
for(iterator = head; iterator != sentinel; iterator = iterator->next)
printf ("%d\n", iterator->val);

return 0;
}

(结束)