本文共 1116 字，大约阅读时间需要 3 分钟。

141 环形链表

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

进阶：

题目给出的接口为：

* Definition for singly-linked list. * struct ListNode {
    *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {
   } * }; */class Solution {
   public:    bool hasCycle(ListNode *head) {
               }};

题目分析

使用快慢指针，利用其中的速度差，如果快慢指针可以相等，那么即证明循环存在。

代码如下：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    bool hasCycle(ListNode *head) {
           if(head == NULL || head -> next == NULL) return 0;        ListNode *p = head , *q = head -> next;        while( p != q)        {
               if(q == NULL || q -> next == NULL) return 0;            p = p -> next;            q = q -> next -> next;        }        return 1;    }};

转载地址：http://tuzfi.baihongyu.com/