首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数:475754 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
判断给定的链表中是否有环。如果有环则返回true,否则返回false。


数据范围:链表长度 ,链表中任意节点的值满足
要求:空间复杂度 ,时间复杂度

输入分为两部分,第一部分为链表,第二部分代表是否有环,然后将组成的head头结点传入到函数里面。-1代表无环,其它的数字代表有环,这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时,对应的链表结构如下图所示:

可以看出环的入口结点为从头结点开始的第1个点(注:头结点为第0个结点),所以输出true。
示例1

输入

{3,2,0,-4},1

输出

true

说明

第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1(注:头结点为位置0),即-4->2存在一个链接,组成传入的head为一个带环的链表,返回true           
示例2

输入

{1},-1

输出

false

说明

第一部分{1}代表一个链表,-1代表无环,组成传入head为一个无环的单链表,返回false           
示例3

输入

{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

输出

true

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
function hasCycle( head ) {
    // write code here
    if(!head){
        return false;
    }
    var slow = head,
        fast = head;
    while(fast != null && fast.next != null){ //之所以要加fast.next != null,是因为避免链表只有一个点的时候,slow.next和fast.next.next都是空的
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

发表于 2021-04-12 22:52:54 回复(0)
首先,知道用双指针就好办了
1.空链表无环
2.找一个循环条件,快指针如果走到空,说明链表无环,确定循环条件
3.循环内部还有一个特殊情况,快指针指向了最后一个节点,再走一步就指向空需要特殊判断。
/**
 * 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)
        {
            return false;
        }
        ListNode *slow=head;
        ListNode *quickly=head;
        while(quickly!=NULL)
        {
            quickly=quickly->next;
            if(!quickly)
            {
                return false;
            }
            if(slow!=quickly)
            {
                quickly=quickly->next;
                slow=slow->next;
            }
            else
            {
                return true;
                break;
            }
        }
        return false;
    }
};

发表于 2021-03-14 14:10:26 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {


          return f2(head);

    }
    //比较笨的办法
    public boolean f1(ListNode head){

        ListNode tmpNode=head;
        if(head==null){
            return false;
        }
        while(tmpNode.next!=null){
            //简单条件判断直接跳出
            if(tmpNode==tmpNode.next){
                return true;
            }

            //临时存储当前节点后继节点
            ListNode next=tmpNode.next;
            //临时头节点遍历
            ListNode tmpHead=head;
            //遍历检测到当前节点
            while(tmpHead!=tmpNode&&tmpHead.next!=null){
                //判断后继是否引用了之前的节点
                if(tmpHead==next){
                    return true;
                }
                tmpHead=tmpHead.next;
            }
            //判断下一个节点
            tmpNode=tmpNode.next;

        }
        return false;
    }

    //看了大佬的题解,使用快慢指针
    public boolean f2(ListNode head){

        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;

        //使用快慢指针,一个跑的快一个跑的慢,如果最后能相遇一定是有环的,毕竟有环一直循环嘛
        //写题的时候注意一下空指针的问题,需要考虑全面,别粗心
        while(fast!=null&&fast.next!=null){

            //指向后继的后继走的快些
            fast=fast.next.next;
            //标准的指向后继走的慢些
            slow=slow.next;
              //如果有环定会相遇
            if(slow==fast){
                return true;
            }
        }

        return false;



    }


}
发表于 2020-11-24 13:42:21 回复(0)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
    判断链表是否有环,用快慢指针
    */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 判断是否重合
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
}

发表于 2020-11-15 01:22:08 回复(0)
//使用集合判断是否有相同对象的地址出现
    public boolean hasCycle(ListNode head) {
        if (head==null){
            return false;
        }
        ArrayList list = new ArrayList();
        boolean flag = false;
        while (head.next != null) {
            list.add(head);
            head = head.next;
            if (list.contains(head)) {
                flag = true;
                break;
            }
        }
        return flag;
    }
}
发表于 2020-09-09 21:34:53 回复(0)
每次访问一个节点,将该节点的next指向head,那么如果存在环,head将再次被访问;
class Solution {
public:
    bool hasCycle(ListNode *head) {
       if (!head) return false;
	ListNode *p=head, *k;
	while (p != NULL && p->next != head)
	{
		k = p->next;
		p->next = head;
		p = k;
	}
	if (!p) return false;
	else return true; 
    }
};


发表于 2020-04-20 14:53:02 回复(0)
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode low = head, fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
            if (low == fast) {
                return true;
            }
        }
        return false;
    }
}

发表于 2019-01-21 12:46:05 回复(0)
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
            return false;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                return true;
        }
        return false;
        
    }
}

发表于 2018-06-09 22:10:32 回复(2)
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        
        if(!head)
            return false;
        ListNode *fast = head,*slow = head;
        while(fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow==fast)
                return true;
        }
        return false;
    }
};

发表于 2017-07-04 11:37:53 回复(0)
用哈希表就解决了,之前在lc上面刷过
class Solution:
    def hasCycle(self , head ):
        # write code here
        dic=set()
        while head:
            if head in dic:
                return True
            dic.add(head)
            head = head.next
        return False


发表于 2021-08-22 12:07:42 回复(1)
//快慢指针能相遇说明有环!
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
            return false;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                return true;
        }
        return false;  
    }
}

发表于 2016-06-20 21:15:36 回复(30)
//遍历链表的同时,让前一个节点的next指向head(或者是任意一个指定的内存),
//在后续的遍历中,如果有节点的当前next指向了head,则说明有环。
//破坏链表,达到最快
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        while(p!=null){
            ListNode aft = p.next;
            if(aft==head) return true;
            p.next=head;
            p=aft;
        } 
        return false;
    }
}

编辑于 2017-09-19 17:44:41 回复(21)

https://leetcode.com/problems/linked-list-cycle/

思路1:hash map

开一个哈希表,标记访问过的节点,如果重复访问了某一节点,说明有环。需要额外O(n)的空间复杂度。

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*, bool> m;
        while (head) {
            if (m.find(head) != m.end()) return true;
            m[head] = true;
            head = head->next;
        }
        return false;
    }
};

思路2:快慢指针

用一快一慢指针,开始两个指针都指向链表头部。慢指针每次向前走一步,快指针每次向前走两步。如果有环,则两个指针最终一定会相遇。这种方法无须额外的空间。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

相关: http://ihuafan.com/%E7%AE%97%E6%B3%95/floyds-cycle-finding-algorithm

发表于 2017-02-08 09:24:33 回复(6)
不得不说Python在这种可以空间换时间的算法中具有天然的优势。
class Solution:
    def hasCycle(self , head ):
        visited_nodes = []  # 记录访问过的结点
        p = head
        while p and p.next:
            if p.next in visited_nodes: # Python的 in 操作,简洁明快
                return True
            visited_nodes.append(p)
            p = p.next
        return False


发表于 2020-09-16 11:08:28 回复(4)
思路就在理解环的意思,头尾相接为环,尾和链中任意节点相接也可以连成环
发表于 2021-01-30 14:32:33 回复(0)
Java:
/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow = head, fast = head;
        while (slow.next != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}
C++:
/**
 * 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== nullptr) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow->next!= nullptr && fast->next!= nullptr && fast->next->next!= nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow==fast) return true;
        }
        return false;
    }
};
C:
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
#include <stdbool.h>
#include <stddef.h>
bool hasCycle(struct ListNode *head) {
    // write code here
    if (head == NULL) return false;
    struct ListNode *slow = head, *fast = head;
    while (fast!=NULL && fast->next!=NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

编辑于 2021-02-04 09:44:50 回复(0)
#include <stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    // write code here

    int  i = 0;

    while (head && i <= 10000) {
        i++; head = head->next;
    }
    
    if (i > 10000) {
        return  true;
    }

    return  false;
}

发表于 2023-01-16 16:53:15 回复(0)
通俗易懂
bool hasCycle(struct ListNode* head ) {
    // write code here
/*
遍历链表,
对每一个遍历过的节点进行处理:next = self
当遍历到next == self时,说明有环,next == NULL时,说明无环
*/
    while(head){
        // 判定
        if(head->next == NULL)
            return false;
        else if(head->next == head)
            return true;
        
        // 处理
        struct ListNode *next = head->next;
        head->next = head;
        
        // 遍历
        head = next;
    }
    
    // head == NULL
    return false;
}


发表于 2021-08-25 13:40:31 回复(1)
利用java的面对对象特性求题解, 遍历链表同时, 将每个节点存入list, 拿到当前节点时, 先判断list中是否包含此节点 , 如包含 , 则有环, 方法直接返回true .
遍历完链表则代表没有环,返回false . 核心是利用对象的唯一性进行比对;
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        ArrayList<ListNode> list = new  ArrayList<ListNode>();
        while(head!=null){
            if(list.contains(head)){
                return true;
            }
            list.add(head);
            head = head.next;
        }
        return false;
    }
}

发表于 2023-02-28 13:53:16 回复(2)
没说不可以改节点值^^
func hasCycle( head *ListNode ) bool {
   cur := head for { if cur == nil { return false  } if cur.Val == 100001 { return true  }
      cur.Val = 100001  cur = cur.Next
   }
}

发表于 2022-08-03 19:58:31 回复(1)