链表中的双指针
学习链表的时候，其添加，删除等操作的复杂度O（1）比较高效，但对其遍历查询复杂度O（n）较高，而且非常不灵活。所以，链表中引入双指针来解决特定问题。
这里说的链表，头结点就是第一个节点，而非伪头结点。
1，环形链表
给定一个链表，判断链表中是否有环。
算法：快慢指针指向头结点，块指针走2步，慢指针走1步。如果没有环，快指针将停在链表的末尾。如果有环，快指针最终将与慢指针相遇。（原理：就像跳棋，路径为链表，同时开始，两个棋跳的步数相同时即为相遇）
复杂度分析：时间复杂度O（n）;因为只增加了快慢指针的内存空间，空间复杂度O（1）。
对比于哈希表解决这个问题，空间复杂度O（n）；快慢指针的优势在于内存占用较少。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public 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;
}
}
给定一个链表，返回链表开始入环的第一个节点。
算法：（1）先在上题的基础上，找到快慢指针相遇节点（不一定为入环第一个节点）（2）慢指针指向头结点，快慢指针再次相遇即为入环第一个节点。（小编也不知道这是步骤2的设计原因，请大神指教）。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow) break;
}
if(fast == null || fast.next == null) return null;
slow = head;
while(fast != slow){
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
找到两个单链表相交的起始节点。
算法：根据相交时，路程相等原理。两个指针分别指向两链表的头结点，同时遍历链表，到达尾节点后指向另一个链表的头结点，直至两结点相等（相交），即为相交的起始结点。
leetcode代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/**
定义两个指针，第一轮让两个到达末尾的节点指向另一个链表的头部，最后如果相遇则为交点
两个指针等于移动了相同的距离，有交点就返回，无交点就是各走了两条指针的长度
*/
if(headA == null || headB == null){
return null;
}
ListNode pA = headA,pB = headB;
// 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头，而第二轮体现在如果
//pA或pB相交就返回交点，不想交最后就是null == null
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
算法：前后指针，设定距离为n不变。指针一起移动，等前指针先到达链表尾（Null），此时后指针指向链表的倒数第n个节点的前一个节点，删除其后节点即可。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
for(int i = 1;i <= n+1;i++){
first = first.next;
}
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
leetcode提供了一个模板，用于解决链表中的双指针问题。
// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow != null && fast != null && fast.next != null) {
slow = slow.next; // move slow pointer one step each time
fast = fast.next.next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem