题目：19. Remove Nth Node From End of List
分析：典型的利用双指针法解题。首先让指针first指向头节点，然后让其向后移动n步，接着让指针sec指向头结点，并和first一起向后移动。当first的next指针为NULL时，sec即指向了要删除节点的前一个节点，接着让first指向的next指针指向要删除节点的下一个节点即可。注意如果要删除的节点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。
解法一：
1 class Solution { 2 public: 3 bool hasCycle(ListNode *head) 4 { 5 ListNode *slow = head, *fast = head; 6 while (fast && fast->next) 7 { 8 slow = slow->next; 9 fast = fast->next->next; 10 if (slow == fast) return true; 11 } 12 return false; 13 } 14 };
如下图所示，X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
解法一：
1 class Solution { 2 public: 3 ListNode *detectCycle(ListNode *head) 4 { 5 if (head == NULL || head->next == NULL) 6 return NULL; 7 ListNode * p = head; 8 ListNode * q = head; 9 while (q != NULL && q->next != NULL)//第一次pq相遇 10 { 11 p = p->next; 12 q = q->next->next; 13 if (p == q) break; 14 } 15 16 if (p == q) 17 { 18 p = head; 19 while (p != q)//从起点开始，在入口点相遇 20 { 21 p = p->next; 22 q = q->next; 23 } 24 return p; 25 } 26 return NULL; 27 } 28 };
原文：https://www.cnblogs.com/sunbines/p/10608202.html