Linked List Cycle

Question

  1. Given a linked list, determine if it has a cycle in it.
  3. Example
  4. Given -21->10->4->5, tail connects to node index 1, return true
  6. Challenge
  7. Follow up:
  8. Can you solve it without using extra space?

题解 - 快慢指针

对于带环链表的检测，效率较高且易于实现的一种方式为使用快慢指针。快指针每次走两步，慢指针每次走一步，如果快慢指针相遇(快慢指针所指内存为同一区域)则有环，否则快指针会一直走到NULL为止退出循环，返回false.

快指针走到NULL退出循环即可确定此链表一定无环这个很好理解。那么带环的链表快慢指针一定会相遇吗？先来看看下图。

Linked List Cycle

在有环的情况下，最终快慢指针一定都走在环内，加入第i次遍历时快指针还需要k步才能追上慢指针，由于快指针比慢指针每次多走一步。那么每遍历一次快慢指针间的间距都会减少1，直至最终相遇。故快慢指针相遇一定能确定该链表有环。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @return: True if it has a cycle, or false
  18.      */
  19.     bool hasCycle(ListNode *head) {
  20.         if (NULL == head || NULL == head->next) {
  21.             return false;
  22.         }
  24.         ListNode *slow = head, *fast = head->next;
  25.         while (NULL != fast && NULL != fast->next) {
  26.             fast = fast->next->next;
  27.             slow = slow->next;
  28.             if (slow == fast) return true;
  29.         }
  31.         return false;
  32.     }
  33. };

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     public boolean hasCycle(ListNode head) {
  14.         if (head == null || head.next == null) {
  15.             return false;
  16.         }
  18.         ListNode slow = head;
  19.         ListNode fast = head;
  20.         while (fast.next != null && fast.next.next != null) {
  21.             slow = slow.next;
  22.             fast = fast.next.next;
  23.             if (slow == fast) {
  24.                 return true;
  25.             }
  26.         }
  27.         return false;
  28.     }
  29. }

源码分析

  1. 异常处理，将head->next也考虑在内有助于简化后面的代码。
  2. 慢指针初始化为head, 快指针初始化为head的下一个节点，这是快慢指针初始化的一种方法，有时会简化边界处理，但有时会增加麻烦，比如该题的进阶版。

复杂度分析

  1. 在无环时，快指针每次走两步走到尾部节点，遍历的时间复杂度为 $$O(n/2)$$.
  2. 有环时，最坏的时间复杂度近似为 $$O(n)$$. 最坏情况下链表的头尾相接，此时快指针恰好在慢指针前一个节点，还需 n 次快慢指针相遇。最好情况和无环相同，尾节点出现环。

故总的时间复杂度可近似为 O(n).

Reference