快慢指针的总结

1.什么是快慢指针

快慢指针就是定义两个指针，移动的速度一快一慢

2.快慢指针使用的情况

2.1找中间值

   对于找找中间值，如果是数组，可以直接返回相应的数组下标，进而找到对应的值，但是对于链表，使用快慢指针找中间值是非常方便的，我们把一个链表当成一个跑道，如果a的速度是b的两倍，那么当a跑完全程，b跑到路程的一般，按照这样的思路找到中间节点。

给定一个链表，请判断该链表是否为回文结构。

public class Solution {
 public boolean isPail (ListNode head) {
        ListNode fast =head;
        ListNode slow= head;
        //如果只有一个节点返回true
        if(fast.next==null){
            return true;
        }
        //多个节点，找出中间值
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //如果节点是奇数个，slow刚好在中间的位置，如果节点是偶数个，节点在前半部分的最后一个，所以slow需要往后多走一个
        slow=slow.next;
        //对后半部节点进行反转
        slow = reverse(slow);
        fast =head;
        while(fast!=null&&slow!=null){
            if(fast.val!=slow.val){
                return false;
            }
            fast =fast.next;
            slow=slow.next;
        }
        
        return true;

    }
    //反转函数
    public ListNode reverse(ListNode head){
       ListNode Phead = new ListNode(0);
       Phead.next =head;
       ListNode p=Phead;
       ListNode h=head;
       ListNode t= h.next;
       h.next=null;
       while(t!=null){
           ListNode m = t;
           t=t.next;
           m.next=p.next;
           p.next = m;
       }
       return Phead.next;
         
    }
}

2.2判断链表中的环

快慢指针中，因为每一次移动后，快指针都会比慢指针多走一个节点，所以他们之间在进入环状链表后，不论相隔多少个节点，慢指针总会被快指针赶上并且重合，此时就可以判断必定有环

 * 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 =null;
        slow=head;
        ListNode fast =null;
        fast = head.next;
        while(slow!=fast){
            if(fast==null||fast.next==null){
                return false;
          }
            slow=slow.next;
            fast =fast.next.next;
        }
        return true;
        
        
    }
}

2.3删除倒数第n个节点

删除倒数第n个节点，一开始让fast指针比slow指针快n+1个元素，接下来，两个指针一步一步往下走，当fast指针走完时，slow指针刚刚好停留在第n-1个元素上。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
  
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
     
        ListNode slow =head;
        //先到第n+1个元素
        while(n-->0&&fast!=null){
            fast=fast.next;
        }
        //如果fast==null,说明第一个元素就是倒数第n个元素
        if(fast==null){
                return head.next;
            }
            //如果不是，继续直到fast.next==null,此时slow.next值是倒数第n个值，将其删除
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return head;
        // write code here
    }
}