链表指针转动，很容易转晕，介绍其中有几个常见的技巧。
一.指针/引用含义
指针/引用，实际上都是存储所指对象内存。
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
二.指针丢失和内存泄漏
插入节点时，注意操作顺序。
删除节点时，注意释放空间。
三.哨兵
哨兵结点的链表叫做带头链表，这样节省判断head == null
四.边界条件
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
- 链表结点位置，在头部，中部，尾部的相关操作，是否能正常工作？
五.常见问题
5.1 链表反转
注意：指针的反转
代码语言：javascript复制public void reverseList(){
Link resLink = null;
Link prevLink = null;
Link curLink = first;
while (curLink != null){
//记录下一个结点
Link nextLink = curLink.getNext();
if(nextLink == null){
//所有结点遍历完毕
resLink = curLink;
}
//指针反转，指针向前
curLink.setNext(prevLink);
prevLink = curLink;
curLink = nextLink;
}
Assert.assertNotNull(resLink);
}5.2 链表中环的检测
注意：快慢指针方式，快指针是慢指针的两倍。
代码语言：javascript复制public boolean checkCire(){
boolean result = false;
if(first == null){
return result;
}
Link fast = first.getNext();
Link slow= first;
//快指针与慢指针相差两步，如果有环，会一直循环，总会相碰。
while (fast!= null && fast.getNext() != null){
fast = fast.getNext().getNext();
slow = slow.getNext();
if(fast == slow){
return true;
}
}
return result;
}5.3 两个有序的链表合并
注意：确定结点头部，中部，尾部的位置判定。
代码语言：javascript复制public Link mergeNode(Link pNode, Link qNode) {
if (pNode == null)
return qNode;
if (qNode == null)
return pNode;
Link p = pNode;
Link q = qNode;
Link resNode = null;
//第一个结点判断
if (p.getData() < q.getData()) {
resNode = p;
p = p.getNext();
} else {
resNode = q;
q = q.getNext();
}
Link node = resNode;
while (p != null && q != null) {
if (p.getData() < q.getData()) {
node.setNext(p);
p = p.getNext();
} else {
node.setNext(q);
q = q.getNext();
}
node = node.getNext();
}
//末尾节点
if (p != null) {
node.setNext(p);
} else {
node.setNext(q);
}
return resNode;
}5.4 删除链表倒数第n结点
注意：快慢指针方式实现，快指针的步数是变动的。
代码语言：javascript复制public void deleteLastKByNode(int k){
Link fast = first;
//计数,排除k等0情况。
int i = 1;
while (fast != null && i < k){
fast = fast.getNext();
}
if(fast == null){
return;
}
Link slow = first;
Link preNode = null;
while (fast.getNext() != null){
fast = fast.getNext();
preNode = slow;
slow = slow.getNext();
}
//头结点删除
if(preNode == null){
first = first.getNext();
}else{
//删除
preNode.setNext(preNode.getNext().getNext());
}
Assert.assertNotNull(first);
}5.5 求链表的中间结点
注意：快慢指针方式，快指针是慢指针的二倍。
代码语言：javascript复制public void findMiddleByNode(){
if(first == null) return;
Link fast = first.getNext();
Link slow = first;
//快指针走完一圈，慢指针半圈
while (fast != null && fast.getNext() != null){
fast = fast.getNext().getNext();
slow = slow.getNext();
}
Assert.assertNotNull(slow);
}5.6 代码
链表
参考
《数据结构与算法之美》
