算法141. 環(huán)形鏈表

1. 題目描述

給定一個鏈表，判斷鏈表中是否有環(huán)。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點(diǎn)。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

進(jìn)階：

你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

來源：力扣（LeetCode）
鏈接： https://leetcode-cn.com/problems/linked-list-cycle

2. 解題思路

/*
解題思路：
解法一、雙指針法
1、設(shè)置一個快指針fast：一次走兩步
2、設(shè)置一個慢指針slow：一次走一步
3、如果存在環(huán)鏈表，則fast和slow會重合
4、否則不存在環(huán)鏈表
*/

3. 測試結(jié)果

解法一、雙指針法

4. C版

/*
title: 算法141. 環(huán)形鏈表
author: xidoublestar
method: 雙指針法
type: C
date: 2020-5-25
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode* head) {
    if (head == NULL)
        return false;
    struct ListNode* fast = head->next, * slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            return true;
    }
    return false;
}

6. 復(fù)雜度分析

解法一、雙指針法
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)