算法-怎样写好链表代码

发表于 | 更新于 | 分类于 | 阅读次数：

上一节讲了链表相关的基础知识，有人可能会说基础知识我都掌握了，但是写链表代码还是很费劲怎么办？确实是这样的，想要写好链表代码并不是容易的事，尤其是那些复杂的链表操作，比如链表反转、有序链表合并等，写的时候非常容易出错。

为什么链表代码这么难写？究竟怎么样才能比较轻松的写出正确的链表代码呢？

只要愿意投入时间，我觉得大多数人都是可以学会的。比如，如果你真能花一整天或者一个周末，就去写链表反转这一个代码，多写几次，知道能毫不费力的写出bug free的代码，这个坎儿还会很难跨吗？

当然，自己有决心并且付出精力是成功的先决条件，除此之外，我们还需要掌握一些技巧和方法。下面我总结了几个写链表的代码技巧，如果能熟练掌握这几个技巧，叫上主动和坚持，轻松拿下链表代码完全没有问题。

理解指针或引用的含义

事实上，看懂链表的结构并不是很难，但是一旦把它和指针混在一起，就很容易让人摸不着头脑。所以要想写好链表代码，首先就要理解好指针。

有些语言有“指针”的概念，比如C语言，有些语言没有指针，取而代之的是“引用”，比如Java、Python等。不管是指针还是引用，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

接下来，我会拿C语言中的指针来讲解。如果你用的是Java或者其他语言也没关系，把它理解成引用就可以了。

实际上，对于指针的理解，只需要记住下面这句话就可以了：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

在编写链表代码的时候，经常会有这样的代码：p->next = q，这行代码是说p结点中的next指针存储了q结点的内存地址。还有一个更复杂的，也是写链表代码经常用到的：p->next = p->next->next，意思是说p结点的next指针存储了p结点的下下一个结点的内存地址。

掌握了指针或者引用的概念，应该可以很轻松的看懂链表代码。

警惕指针丢失和内存泄露

不知道你有没有这样的感觉，写链表代码的时候指针指来指去，一会就不知道指针到哪里了。所以我们在写代码的时候，一定不要弄丢了指针。

如上图所示，当我们在a结点和b结点之间插入结点c，假设当前指针p指向结点a。如果我们将代码写成下面这个样子，就会发生指针丢失和内存泄露。

1
2
p->next = c; // 将p的next指针指向c结点
c->next = p->next; //将c结点next指针指向b结点

当p->next指针在完成第一步操作之后，已经不再指向b结点了，而是指向结点c，因此，第二行代码相当于将c->next指针指向了自己。因此整个链表断裂成了两半，从结点b之后的所有结点都无法访问了。

对于有些语言来说，比如C语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露，所以，我们在插入结点时，一定要注意操作的顺序。要先将c结点的next指针指向b，再将a结点的next指针指向c，这样才不会丢失指针，导致内存泄露。

利用哨兵简化实现难度

首先，我们回顾一下单链表的插入、删除操作。如果我们在结点p之后插入一个结点，只需要下面两行代码就可以了。

1
2
new_node->next = p->next; 
p->next = new_node;

但是当我们向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中head表示链表的头结点。所以从这段代码可以看出，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不同的。

1
2
3
4
if (head == null)
{
	head = new_node;
}

同样再来看一下链表的删除操作，如果要删除p结点的后继点点，我们只需要一行代码就可以搞定：

1
p->next = p->next->next；

但是如果要删除链表的最后一个结点，这样的代码就不行了。跟插入类似，我们也需要对这种情况特殊处理。代码如下：

1
2
3
4
if (head->next == null)
{
	head = null;
}

可以看出，针对链表的插入、删除操作，需要对第一个结点的插入和最后一个结点的删除情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。那如何来解决这个问题呢？

这时上面提到的哨兵就出场了。现实中的哨兵，解决的是国家之间的边界问题。同理我们这里的哨兵也是解决“边界问题的”，不直接参与业务逻辑。

还记得如何表示一个空链表呢？head=null表示链表中没有结点了，其中head表示头结点指针，指向链表中的第一个结点。

如果我们引入哨兵结点，在任何时候，不管链表是不是为空，head指针都会一直指向这个哨兵结点。我们把这种有哨兵的链表叫做带头链表，相反，没有哨兵结点的链表叫做不带头链表。

如下我画了一个带头链表，可以发现，哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑。

实际上，这种利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序、归并排序、动态规划等。这里用C语言实现一个简单的例子，不涉及语法方面的高级知识，你可以类比其他语言。

代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 在数组a中，查找key，返回key所在的位置，其中n代表数组，a代表长度
int find(char* a, int n, char key){
	// 边界条件处理，如果a为空，或者n<=0
	if(a == null || n<=0){
		return -1;
	}

	int i=0;
	// 这里有两个比较操作： i<n 和 a[i] == key
	while(i<n){
		if(a[i] == key){
			retrun i;
		}
		++i;
	}

	retrun -1;
}

代码二：

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
// 在数组a中，查找key，返回key所在的位置，其中n代表数组，a代表长度
// 为了更好的解释，这里举了个例子来说明
// a = {4,2,3,5,9,6} key = 7
int find(char* a, int n, char key){
	// 边界条件处理，如果a为空，或者n<=0
	if(a == null || n<=0){
		return -1;
	}
	// 这里因为要将a[n-1]设为哨兵，所以特殊处理这个值
	if(a[n-1] == key){
		return n-1;
	}
	// 临时变量保存a[n-1]，以便之后恢复，这里temp = 6
	char temp = a[n-1];
	// 把key值放到数组a[n-1]，此时a={4,2,3,5,9,7}
	a[n-1] = key;

	int i=0;
	// 此时while循环比起代码一，少了i<n这个比较操作
	while(a[i] == key){
		++i;
	}
	// 将数组a[n-1] 恢复为原来的值
	a[n-1] = temp;

	// 如果i = n-1，说明数组中没有要找的key
	if(i == n-1){
		return -1;
	}
	// 否则，说明找到了key，位置为i
	else{
		return i;
	}
}

对比两段代码，在字符串a很长的时候，比如几万、几十万，你觉得那段代码执行更快呢？答案是代码二。因为两端代码中执行次数最多的就是while循环那一部分。在第二段代码中，我们通过一个哨兵a[n-1]=key，成功省掉了一个比较语句，不要小看了这一句，当积累上万次、几十万次的时候，累积的时间就很明显了。

当然，这里只是说明哨兵的作用，写代码的时候千万不要写成第二段代码那样，可读性太差了，大部分情况下，我们并不需要追求如此极致的性能。

重点留意边界条件处理

软件开发中，代码在以下边界或者异常情况下，最容易产生bug。链表代码也不例外，要实现没有bug的链表代码，一定要在编写的过程中以及编写完成后，检查边界条件是否考虑全面，以及边界条件下代码是否能运行。

我经常用来检查链表代码是否正确执行的边界条件有这么几个：

  • 如果链表为空时，代码是否能正常工作？
  • 如果一个链表只包含了一个结点，代码能否正常工作？
  • 如果链表只包含两个结点时，代码能否正常工作？
  • 代码逻辑在处理头结点和尾结点时，是否能正常工作？

当你写完链表代码之后，除了看下你写的代码在正常情况下能否工作，还要看下在上面我列举的杰哥边界条件下，代码能否正常工作。

当然边界条件不止我列举的这些，针对不同的场景，可能还有特定的边界条件，需要自己去思考，不过套路都是一样的。

其实，不光是写链表代码，在写任何代码的时候，千万不要只是实现业务正常情况下的功能就行了，一定要多想想会遇到哪些边界情况或者异常情况，遇到了应该如何应对，这样写出来的代码才够健壮。

举列画图，辅助思考

对于稍微复杂的链表操作，比如前面我们提到的单链表反转，指针一会指这，一会指那，总感觉脑容量不够，想不清楚。这时候可以采用举列法和画图法，来进行辅助分析。

你可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉思路清晰很多。比如往单链表中插入一个结点，可以先把各种情况都举一个例子，画出插入前和插入后的链表变化，如图所示：

看着图写代码，是不是简单多了。而且当我们写完代码之后，也可以举几个例子，画在纸上，照着代码走一遍，很容易发现代码中的Bug。

多写多练，没有捷径

如果你已经理解并掌握了这些方法，但是手写代码还是会出现各种各样的错误，也不要着急，多写多练。把常见的链表操作多写几遍，出问题就一点点调试，熟能生巧。

下面我精选了5个常见的链表操作，这要把这几个操作写熟练，不熟就多练几遍，保证之后不会在害怕写链表代码。

  • 单链表反转
  • 链表中环的检测
  • 两个有序链表合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点

我觉得，写链表代码是最考验逻辑思维能力的，因为链表到处都是指针的操作，边界条件的处理，一个不慎就会产生bug。链表代码写的好坏，可以看出一个人写代码是否细心，考虑问题是否全面，思维是否缜密，所以很多面试都喜欢让人手写链表代码。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/**
 * 链表的一些算法题目
 */
public class LinkListAlgorithm {
    public static void main(String[] args) {
        // 第一个链表，检测是否有环
        System.out.println("链表中环的检测");
        Node<Integer> n1 = new Node<>(1);
        Node<Integer> n2 = new Node<>(2);
        Node<Integer> n3 = new Node<>(3);
        n1.next = n2;
        n2.next = n3;
        n3.next = n1; // 1->2->3->1
        System.out.println(isLoop(n1)); // true
        System.out.println("==========================================");
        // 链表反转
        System.out.println("链表反转");
        Node<Integer> n4 = new Node<>(4);
        Node<Integer> n5 = new Node<>(5);
        Node<Integer> n6 = new Node<>(6);
        Node<Integer> n7 = new Node<>(7);
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        System.out.println(printLinkList(n4)); // 4->5->6->7
        Node<Integer> head = reverse(n4);
        System.out.println(printLinkList(head)); // 7->6->5->4
        System.out.println("==========================================");

        // 求链表的中间节点
        System.out.println("求链表的中间节点");
        Node<Integer> n8 = new Node<>(8);
        Node<Integer> n9 = new Node<>(9);
        Node<Integer> n10 = new Node<>(10);
        Node<Integer> n11 = new Node<>(11);
        Node<Integer> n12 = new Node<>(12);
        n8.next = n9;
        n9.next = n10;
        n10.next = n11;
        n11.next = n12; // 8->9->10->11->12
        System.out.println(printLinkList(n8));
        Node<Integer> mid = middle(n8);
        System.out.println("中间节点是： " + mid.val);  // 10
        System.out.println("==========================================");

        // 有序链表合并
        System.out.println("有序链表合并");
        Node<Integer> n13 = new Node<>(13);
        Node<Integer> n14 = new Node<>(14);
        Node<Integer> n15 = new Node<>(15);
        n13.next = n14;
        n14.next = n15;
        System.out.println("第一个链表： "+printLinkList(n8));
        System.out.println("第二个链表： "+printLinkList(n13));
        head = merge(n8, n13);
        System.out.println("合并后的链表： "+printLinkList(head));

        System.out.println("==========================================");
        // 删除倒数第2个节点
        Node<Integer> n16 = new Node<>(16);
        Node<Integer> n17 = new Node<>(17);
        Node<Integer> n18 = new Node<>(18);
        Node<Integer> n19 = new Node<>(19);
        n16.next = n17;
        n17.next = n18;
        n18.next = n19;
        System.out.println("删除前： "+printLinkList(n16));
        head = deleteLastKDesc(n16, 3);
        System.out.println("删除后： "+printLinkList(n16));
    }

    /** 合并两个有序链表 */
    private static Node<Integer> merge(Node<Integer> n1, Node<Integer> n2) {
        // 确定新链表头结点
        Node<Integer> head, p = n1, q = n2;
        if (p.val > q.val){
            head = n2;
            q = q.next;
        }else{
            head = n1;
            p = p.next;
        }
        Node<Integer> r = head;
        while (p!=null &&q!=null){
            if (p.val < q.val){
                r.next = p;
                p = p.next;
            }else {
                r.next = q;
                q = q.next;
            }
            r = r.next;
        }
        if (p!=null){
            r.next = p;
        }else{
            r.next = q;
        };
        return head;
    }

    /**查找链表中间节点*/
    private static Node<Integer> middle(Node<Integer> head) {
        if (head==null) return null;
        Node<Integer> p = head;
        Node<Integer> q = head;
        while (q.next !=null && q.next.next!=null){
            q = q.next.next;
            p = p.next;
        }
        return p;
    }

    /** 链表中环的检测*/
    private static boolean isLoop(Node<Integer> head){
        // 采用快慢指针法 如果两个指针相遇，则说明有环
        Node<Integer> p = head;
        Node<Integer> q = head.next.next;
        while (q!=null){
            p = p.next;
            q = q.next.next;
            if (q == p){
                return true;
            }
        }
        return false;
    }
    /**反转链表*/
    private static Node<Integer> reverse(Node<Integer> head){
        if (head.next == null)return head;
        Node<Integer> p;
        Node<Integer> q;
        Node<Integer> r;
        p = head;
        q = p.next;
        p.next = null;
        while (q != null){
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }
        return p;
    }

    /**删除链表倒数第K个结点*/
    private static Node<Integer> deleteLastKDesc(Node<Integer> head, int k){
        if (head == null || k <0) return null;
        Node<Integer> p = head;

        while (p != null){
            p = p.next;
            k--;
        }
        if (k == 0){
            return head.next;
        }

        if (k < 0){
            p = head;
            while (++k != 0){
                p = p.next;
            }
            p.next = p.next.next;
        }
        return p;
    }

    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E e){
            this.val = e;
        }
    }
    private static String printLinkList(Node<Integer> head){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (head !=null){
            if (head.next !=null)
                sb.append(head.val).append(", ");
            else
                sb.append(head.val);
            head = head.next;
        }
        sb.append("]");
        return sb.toString();
    }
}