[数据结构与算法]Day4 链表-快慢指针

链表题能用到快慢指针的一般是两种题目：yi/

一、判断链表是否存在环结构

要判断是否存在环结构，那么我们就定义一个组快慢指针，让快指针一次动两步而慢指针一次动一步。如果在两个指针动的过程中，快指针指向了null，那么就表示这个链表没有环。如果两个指针在某一时刻是相等的，那么则表示该链表存在环结构。

代码实现如下：

        static bool HasCycle(Node head)
        {
            if(head == null || head.next == null) { return false; }
            Node F = head;
            Node S = head;
            while (F != null && F.next !=null)
            {
                F = F.next.next;
                S = S.next;
                if(F == S) { return true; }
            }
            return false;
        }

二、删除倒数第n个节点

要删除倒数第n个节点我们自然要找到倒数第（n+1）个节点。我们只要找到这个节点，并让他指向下下个节点就能完成删除操作。

那么怎么找呢？我们可以先让快指针走n+1步，此时再让慢指针和快指针一起走直到快指针指向空，这样慢指针走的距离和快指针走完n+1距离链表尾部的距离是一样的。

快指针走过链表总长度L = n+1+和慢指针走的步数=慢指针走的步数+n+1（这样好理解！）那么此时慢指针的位置是在从后往前数 L-慢指针走过的步数 =? n +1 也就是我们想要找的位置！

代码如下：

        static Node RemoveNthFromEnd(Node head,int n)
        {
            if(head == null || head.next == null)
            {
                return null;
            }
            Node F = head;
            Node S = head;
            for (int i = 0; i < n+1; i++)
            {
                F = F.next;
            }
            while (F != null)
            {
                S = S.next;
                F = F.next;            
            }
            S.next = S.next.next;
            return head;
        }