单链表OJ题（课堂总结）

1.链表的带环问题

       

上图就是一个典型的带环链表

   1.1如何判读链表是否带环？ 

   最常见的方法就是利用快慢指针，快指针追加慢指针，当二者相等的时候即可判断链表带环

其实现的代码如下：

bool hasCycle(struct ListNode*head)

{
     struct ListNode* slow = head,*fast = head;

     while(fast && fast->next)

    {

            slow = slow->next;

            fast = fast ->next->next;

            if(slow == fast)

                return true;

    }

           return false;

}

 1.2 为什么快慢指针一定会相遇 

      1.2.1 两指针每走一步其距离缩小1

    假设slow进环的时候fast与其的距离为N，此时每当slow走一步，fast与slow的距离都会缩小1,最后缩小到0，从而两指针相遇。

      1.2.2 两指针每走一步其距离缩小2

初步证明：

  1.N是偶数，第一轮就追上。
       2.N是奇数，第一轮就会错过，距离变成C-1（C为环的长度）。
           a.如果C-1是偶数，下一轮就追上了
           b.如果C-1是奇数，那么就永远追不上

深度证明：

     假设slow进环时，fast跟slow的距离为N

     slow走的距离是：L

     fast走的距离：L+x*C+C-N

     slow进环时，假设fast已经在环里转了x圈

     如果fast走的距离是slow的3倍

     3*L = L+x*C + C-N

     2*L = (x+1)*C-N

    偶数 = （x+1)*偶数-奇数      所以只有两种情况：  N是奇数，C也是奇数

                                                                                   N是偶数时，C也是偶数

    由此可以得出N是奇数且C是偶数不能同时存在，在初步证明中的永远追不上不成立

  把两种情况代入初步证明中可以得出结论

    结论：一定能追上

         N偶数第一轮就追上了

         N是奇数第一轮追不上，C-1是偶数第二轮就追上

 1.3 找环的入口点

    1.3.1 方法一       

一个指针从头结点开始前进，而slow指针在与fast相遇点开始前进,当head指针和slow指针相遇的时候，该点为环的入口点。

证明如下： 

相遇时：

slow走的路程：L + N

fast走的路程：L+x*C+N

fast走的路程是slow的2倍：化简后的公式为：L =x*C-N ->  L = (x-1)*C + C - N

以下为代码的实现：

struct ListNode*meet = slow;

while(meet != head)

{

     meet = meet ->next;

     head = head ->next;

}

      return meet;

1.3.2 方法二 

 

 newhead = meet->next;

  newhead =NULL;

通过上述两个操作，让找环入口点转化为找两个链表的交点问题