本文首发于 LOGI'S BLOG，由作者转载。
引入哨兵
以单链表的插入和删除为例，在节点 p 后插入节点 s 的代码为
s->next = p->next;
p->next = s;
但如果链表为空，以上代码就不再适用了，此时要进行如下特殊处理。
if(head == null) {
head = s;
}
删除节点 p 的代码为
p->next = p->next->next;
但如果 p 是最后一个节点，上面的代码同样无法工作，要做如下特殊处理。
if(p->next == null) {
head = null;
}
可见，对于单链表，对第一个结点的插入和最后一个结点的删除需要特殊处理，实现起来比较繁琐，并且容易因考虑不周而出错，这时，哨兵 就登场了。
哨兵在现实生活中的作用是守卫国家边界，同理，编程方法中的哨兵也是为了处理边界问题。
对于单链表，我们定义第一个结点为哨兵结点，其不存储数据，而是作为链表的头存在，又叫头结点，引入哨兵的链表叫带头链表，以下是带头链表的结构。
head -> [/] -> [a] -> [b] -> [c] -> null
此时，无论链表存不存在数据，都包含一个结点，因此上面说的第一个结点的插入和最后一个结点的删除便无需特殊处理。实际上，很多算法的实现都用到了哨兵，如插入排序，归并排序和动态规划等。
画图和举例
画图有利于理清思路，避免忘记，留更多精力给逻辑思考。而举例有利于发现代码中的错误。
留意边界条件
尽管引入哨兵减化了边界处理，但大多数情况下，仍然要根据具体情况处理边界，为此至少应考虑以下几种情况：
- 若链表为空，代码是否正确
- 若链表仅含一个结点，代码是否正确
- 若链表仅含两个结点，代码是否正确
- 代码在处理头尾结点时能否正常工作
熟练掌握基本操作
反复练习基本操作的编写，以后遇到难题时便可关注问题本质，快速上手解决问题，以下列举一些基本操作。
操作一：单链表反转
// 关键步骤将第一个结点变成尾节点，最后将其 next 置空
public void reverse() {
Node prev = this.head;
Node next = null;
Node current = this.head.next;
// 没有结点或仅有一个结点，无需反转
if (current == null || current.next == null) {
return;
}
// 第一个有效结点变为尾结点
this.tail = current;
// 从第一个有效结点开始逆向 next 指针
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// 头指针指向最后一个结点
this.head.next = prev;
// 尾指针置空
this.tail.next = null;
}
操作二：链表中环的检测
步骤：定义快慢指针，快指针每次走一步，慢指针每次走两步，若最终两者相遇，则链表必存在环。
证明：首先，由于链表中存在环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程（长跑时你领先别人数圈，从后面追赶别人）。可用数学归纳法证明两者必然相遇。
- 快指针与慢指针相差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
// 再走一步，fast 和 slow 将在结点 E 相遇
head -> A -> B -> C -> D -> E
| fast slow |
I <- H <- G <- F
- 快指针与慢指针相差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相差一步，变为情况 1。
// 再走一步，fast 和 slow 将相差一步
head -> A -> B -> C -> D -> E
| |
I <- H <- G <- F
slow fast
- 快指针与慢指针相差 n (n>2) 步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差 (n+1-2) = n-1 步。n-1 次将变为情况 1。
由此可得，两者必然相遇。下面证明，算法的时间复杂度为 O(n)。
- 慢指针进环时，快指针必然处于环中，且两者相差步数小于等于圈长 L。
- 因为快指针速度是慢指针的两倍，所以慢指针走了 L 步时，快指针走了 2L 步，快指针比慢指针多走了 L 步，此时两者必然相遇或已经相遇。
可见，慢指针最多遍历一遍链表，两者便会相遇，算法的时间复杂度为 O(n)。
public boolean containsCircle() {
Node slow = this.head.next;
// 让 fast 领先一步，否则两者直接相等
Node fast = slow.next;
if (slow == null) {
return false;
}
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
引申：获得链表中环的入口点
步骤：假设环长为 L，定义两个指针 p 和 q，从 head 开始以步长为 1 往后遍历，首先让 q 先走 L 步，之后两者同时向后遍历，相遇时即到达环的入口点。
那么，环长如何求解那，利用上面证明链表中含有环的方法。快慢指针相遇时记录相遇点，随后慢指针继续遍历，直到再次经过相遇点时所走步数即为环长。
public Node getCircleEntry() {
Node slow = this.head.next;
Node fast = slow.next;
Node meetPoint = null;
int circleLength = 0;
if (slow == null) {
return null;
}
// 保存相遇点
while (fast != null && fast.next != null) {
if (slow == fast) {
meetPoint = slow;
break;
}
slow = slow.next;
fast = fast.next.next;
}
do {
slow = slow.next;
circleLength++;
}
while (slow != meetPoint);
// 计算环长
slow = fast = this.head.next;
for (int i = 0; i < circleLength; i++) {
fast = fast.next;
}
// 获得入口点
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
操作三：两个有序链表的合并
public void merge(SinglyLinkedListReview list) {
// 保存 p 的前驱，为前插做准备
Node pPre = this.head;
Node p = pPre.next;
Node q = list.head.next;
// 第二个链表为空，无需合并
if (q == null) {
return;
}
// 第一个链表为空，直接将 head 指向第二个链表第一个有效结点
if (p == null) {
this.head.next = q;
return;
}
while (q != null) {
// q 每次都要走一步，保存 q 后继，以免覆盖
Node qNext = q.next;
// 当链表一当前结点小于链表二当前节点时，p 走一步
if (p.data < q.data) {
q.next = p.next;
p.next = q;
p = q.next;
pPre = q;
} else {
q.next = p;
pPre.next = q;
pPre = q;
}
q = qNext;
// 第一个链表走到结尾，直接将 p 指向 q
if (p.next == null) {
p.next = q;
this.tail = list.tail;
break;
}
}
}
操作四：删除链表倒数第 n 个结点
步骤：求表长 L，获取正数第 L-n+1 个结点的前驱结点，删除。
public void deleteLastIndexOf(int index) {
int listLength = 0;
Node p = this.head.next;
// 无有效结点，返回
if (p == null) {
return;
}
// 求表长
while (p != null) {
p = p.next;
listLength++;
}
// index 合法性判断
if (index > listLength) {
return;
}
// 获取 p 前驱结点
Node pPre = this.head;
for (int i = 0; i < listLength - index; i++) {
pPre = pPre.next;
}
// 判断 p 是否为尾结点
if (pPre.next.next == null) {
this.tail = pPre;
}
pPre.next = pPre.next.next;
}
操作五：求链表的中间结点
步骤：定义快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走至表尾时，慢指针走至中点。
public Node getMidPoint() {
Node slow = this.head.next;
Node fast = this.head.next;
if (slow == null) {
return null;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 结点个数为偶数时，返回上中点
return slow;
}
网友评论