目录
链表的基本操作
- 改/遍历：
while(?) - 查： 返回倒数K个节点
- 增/删除：反转链表，删除链表中的重复节点II
链表的一种重要题型 ： 快慢指针
- 回环链表
- 环路检测
- 将有序链表转换成平衡BST
PART I ： 链表的基本操作
改/遍历
因为链表不是像数组一样占用了连续地址的结构，所以很难通过索引（index）的方式进行存取，同时我们也没有办法不通过一次遍历就知道链表的元素个数。它的访问和修改往往需要通过通过一个指针，并非C语言意义上的指针（pointer），而更应该被称作游标（cursor），如果没有说明，下文还是通过指针这个词代指链表中访问节点的指示器。
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
ListNode cur = head;
while (cur != null) {
cur = cur.next;
}
增
比如，向链表中结尾后面新增加一个节点，节点的值为-1：
public void addEnd(ListNode head){
ListNode cur = head;
while(cur.next != null){
cur = cur.next;
}
cur .next = new ListNode(-1);
}
再比如，向链表（链表的元素是不重复的）中的元素4前面增加一个数值为6的节点：
public void addBefore4(ListNode head){
ListNode cur = head;
while(cur.next.val != 4){
cur = cur.next;
}
ListNode temp = cur.next;
cur.next = new ListNode(6);
cur.next.next = temp;
}
上面几个例子的难点都在于：while(?)，while语句中需要填什么内容？
while(?)
什么时候使用cur.next 什么时候用cur？这个地方涉及到对while()语句的理解。我们可以形象地引入英语中的两个概念，英语的将来时（cur.next）和完成时(cur)。
cur.next!=null这个判断条件表示当跳出while循环时，cur.next == null，即cur 将要将链表迭代完，而cur == null ，表示指针cur已经将链表迭代完成。
cur != null 同理：
至于while的条件判断填什么内容，一般来说，如果是单纯迭代链表的话，使用cur!=null，如果想做插入，删除等等操作，需要利用被插入/删除的前一个节点的的话，则需要cur.next != null。
下面看看两个题目，加深对while(?)这个问题的理解：
反转链表
第一种思路：头插法
头插法的时候需要使用在做链表相关问题中的一个非常重要的性质，dummy节点（空头结点），它的重要性，后面都会有体现：
头插法的示意图
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode cur = head;
while(cur!= null){
ListNode node = new ListNode(cur.val);
node.next = dummy.next;
dummy.next = node;
cur = cur.next;
}
return dummy.next;
}
这种方法在实现过程中，其实吧原来的链表head，重新复制了它的值，创建了新的链表，内存开销很大。
第二种思路：交换元素法
具体代码如下：
public ListNode reverseList(ListNode head){
ListNode cur = head;
ListNode pre= null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
返回倒数K节点
思路很简单，通过两个指针就可以确定一个“标尺”，通过这个标尺往下走，直到标尺的底端碰到链表的最后一个节点。很明显，当K=2时，因为链表的最后一个节点是5（本题中），倒数第二个节点应该是4，应当使用“将来时”，即cur.next != null 。
返回倒数K节点
代码如下：
class Solution {
public int kthToLast(ListNode head, int k) {
ListNode cur = head;
while( -- k > 0)
cur = cur.next;
ListNode p = head;
while(cur.next != null){
cur = cur.next;
p = p.next;
}
return p.val;
}
}
删除排序链表中的重复节点II
此外，大家可能对dummy节点的使用理解不够深入，这里再给出一道题：
删除排序链表中的重复节点II
排序链表的重复节点一定是相邻的，根据题意，一旦有重复的节点就会全部删除。所以我们很容易想到，通过一个指针cur记录当前节点的位置，cur.next 和 cur.next.next比较后面有没有节点重复，如果一旦有重复，就通过temp节点搜索到没有重复的节点，直接连接到cur的下一个：
这里用的是指针的完成时，所以可以看到当指针cur.next指向temp的时候并没有消除2和3之间的指针。不给过这个题这样写也是ac的，如果要改掉这里的话可以使用指针的将来时。
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = head;
ListNode cur = dummy;
while(cur.next != null && cur.next.next!= null){
if(cur.next.val == cur.next.next.val){
ListNode temp = cur.next;
while(temp != null && temp.val == cur.next.val){
temp = temp.next;
}
cur.next = temp;
}else
cur = cur.next;
}
return dummy.next;
}
PART II： 快慢指针
直接通过一道题目来解释快慢指针的概念：
环路检测
如果在链表中存在环，则返回环的入口，在这个题目中就是第三个节点。这道题可以分解成两个子问题：判断链表是否存在环路，如果存在环路，返回环路的入口。
判断是否存在环路
闪电侠和你在一个环形的赛道上跑步，你刚迈出腿，闪电侠就和你相遇了。
如果链表中存在环的话，存在这一快一慢两个指针，这两个指针在若干次迭代后必然相遇。
直接看看代码：
class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
但是一般情况下，快慢指针使用的代码模板是这样的：
//完成时 后中
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
//将来时 前中
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
我们下面来分析这段代码.
完成时+当链表节点为偶数时：
很明显，当迭代刚刚结束时，slow恰好在偶数链表的中间的后半部分，所以这样的情况我称之为“后中”。
完成时+当链表节点为奇数时：
slow节点指向的是链表的正中间节点
将来时+当链表节点为偶数时：
与上面的相对应的，这中情况被称为前中。
将来时+当链表节点为奇数时：
和上面完全相同。所以我们可以知道，指针的将来时和完成时分别影响的是slow指针的位置，分成了“前中”和“后中”两种情况。具体的我们再来分析。
如何找出环路的入口
大致上知道了快慢指针的找环是否存在的流程之后，我们看看如何找到入口。
设慢指针slow在和快指针fast第一次相遇走过的节点的距离为ls，快指针走过的距离为lf，其中m为链表的第一个节点到环形入口的距离，环的距离为r，环的入口到两个指针相遇的距离为d，如图，则有以下的关系：
ls = m + d;
lf = m + d + n*r
快指针可能在整个环内走了n圈，但是因为快慢指针同时出发，两个指针也满足如下关系：
ls*2 = lf
m + d = n * r
m = (n-1)*r + r - d
当快慢指针相遇时，如果把慢指针放回起点，快指针在相遇点继续走，当慢指针走完m，快指针就回走完r-d，再次相遇时就是链表的入口，代码如下：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next!= null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) break;
}
if(fast == null || fast.next == null) return null;
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
这里采用了fast的完成时，如果没有回环的话直接遍历完毕整个链表，退出while。
此外快慢指针的应用除了检测环路之外，还可以利用上述的“前中”或者“后中”，找到链表的中间节点。
将有序链表变成平衡二叉搜索树
要想变成平衡二叉搜索树肯定要找中间的节点。使用后中法或者前中法都行，这里使用的是的后中法：
将有序链表变成平衡二叉搜索树
class Solution {
public ListNode findMiddleElement(ListNode node){
ListNode prev = null;
ListNode slow = node;
ListNode fast = node;
while(fast != null && fast.next != null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if(prev != null) prev.next = null;
return slow;
}
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
ListNode mid = findMiddleElement(head);
if(mid == head) return new TreeNode(mid.val);
TreeNode midTreeNode = new TreeNode(mid.val);
midTreeNode.left = sortedListToBST(head);
midTreeNode.right = sortedListToBST(mid.next);
return midTreeNode;
}
}
网友评论