双指针技巧套路-链表
# 双指针技巧套路
双指针一般有两种类型快慢指针和左右指针。快慢指针一般用于链表或者数组中需要删除、移动等情况。左右指针一般用于数组查询等情况。
# 快慢指针
题目：
142. 环形链表 II (opens new window)
876. 链表的中间结点 (opens new window)
剑指 Offer 22. 链表中倒数第k个节点 (opens new window)
21. 合并两个有序链表 (opens new window)
# 环形链表
题目：
思想：
定义两个快慢指针，快指针做一定限制，然后快指针和慢指针依次往后走， 快指针依次往后走两个，如果当快指针遇到慢指针（相当于跑步超了一圈），这时候就说明有环。
代码：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}
# 环形链表II
题目：
思想：
可以把这题想成一个一部分是直线跑道，另一部分是环形跑道，一旦进入环形跑道就一直在环形跑道跑步的情况。那么现在有A和B节点，B跑得比较快，A和B会在环形跑道相遇。
设A这时候跑步的距离为k，那么B这时候的跑步距离一定是2k。设A在环形跑道跑了m距离，那么直线跑道的距离为
k-m。那么可以算出B在环形跑道跑路的距离为2k-(k-m)=k+m。而B能够在环形跑道和A第一次相遇，说明B在环形跑道跑路的距离是比A跑步的距离多了一圈，故我们能算出一圈的距离为：k
此刻我们发现从相遇点到环形跑步的起点的距离为：k-m，而从直线跑道起点到环形跑道起点的距离也为：k-m。
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
# 链表的中间节点
题目：
思想：
快慢指针依次遍历链表，当快指针到达链表结尾，返回慢指针的位置。
代码：
public class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
# 链表中倒数第k个节点
题目：
思想：
先让快指针移动k次，然后快慢一起向后移动，快指针到达链表末尾的时候，返回慢指针即可。
代码：
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast, slow;
fast = slow = head;
for(int i = 0; i < k; i++) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
# 合并两个有序链表
题目：
思想：
运用头指针的技巧，然后用两个指针分别遍历两个链表，较小节点加入链表即可。
代码：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 头结点
ListNode head = new ListNode(-1), p = head;
ListNode p1 = list1, p2 = list2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return head.next;
}
}
# 相交链表
题目：
思想：
这道题类似与环形链表，两个链表所走路的不同是因为他们在相交节点前所走的路不同，所以只要让两个链表节点，先走完自己的路，然后再走对方在相交节点之前的路就可以保证两者同时达到同一节点。
代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p != q) {
if(p == null) {
p = headB;
} else {
p = p.next;
}
if(q == null) {
q = headA;
} else {
q = q.next;
}
}
return q;
}
}