精华内容
下载资源
问答
  • 比如一个单链表a->b->c->d->e->f,如果从d指向b,构成的环是否有意义呢?
  • 先判断链表是否相交,我们可以运用两个链表相交后就变成了一条链表这个特性来判断,因为如果两条链表相交,那么这两条链表的最后一个节点一定一个节点,否则不可能相交 //1表示有交点,0表示没有交点 int ...

    先理解一下题目的意思,单链表的相交和普通两条线的相交一样吗?
    在这里插入图片描述
    所以当我们把其换成节点就可以变成下面这样:

    在这里插入图片描述
    先判断链表是否相交,我们可以运用两个链表相交后就变成了一条链表这个特性来判断,因为如果两条链表相交,那么这两条链表的最后一个节点一定是同一个节点,否则不可能相交

    	//1表示有交点,0表示没有交点
    	int IsIntersection(Node *first1, Node *first2)
    	{
    		assert(first1);
    		assert(first2);
    		while (first1->next != NULL)
    		{
    			first1 = first1->next;
    		}
    		while (first2->next != NULL)
    		{
    			first2 = first2->next;
    		}
    		if (first1 == first2)
    		{
    			return 1;
    		}
    		return 0;
    	}
    
    

    接下来,我们考虑交点的问题,如何才能找到交点?
    两条链表在交点之后的长度肯定是一样的,在交点之前的长度是不一样的,我们可以计算出两条链表长度的差值k,然后让长的链表先走k步,再让两条链表同时走,当相同的时候,就表示走到交点了,这时候返回即可
    在这里插入图片描述

    	int GetLength(Node *first)
    	{
    		assert(first);
    		int count = 0;
    		while (first != NULL)
    		{
    			count++;
    			first = first->next;
    		}
    		return count;
    	}
    
    	Node *IntersectionNode(Node *first1, Node *first2)
    	{
    		assert(first1);
    		assert(first2);
    		int count1 = GetLength(first1);
    		int count2 = GetLength(first2);
    		Node *longer = first1;
    		Node *shorter = first2;
    		int k = count1 - count2;
    		if (count1 < count2)
    		{
    			longer = first2;
    			shorter = first1;
    			k = count2 - count1;
    		}
    		while (k--)
    		{
    			longer = longer->next;
    		}
    		while (longer != shorter)
    		{
    			longer = longer->next;
    			shorter = shorter->next;
    		}
    		return longer;
    	}
    
    展开全文
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示...hash表遍历所有节点,每次遍历到一个节点时,

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    如果链表中存在环,则返回 true 。 否则,返回 false 。

    进阶:

    你能用 O(1)(即,常量)内存解决此问题吗?

    题解方法一:

    hash表遍历所有节点,每次遍历到一个节点时,判断该节点此前是否被访问过。
    复杂度分析
    时间复杂度:O(N),其中 N 是链表中的节点数。
    空间复杂度:O(N),其中 NN 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。

    count()返回集合中某个值元素的个数

    /**
     * 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) {
            //使用hash表,遍历一次;
            unordered_set<ListNode*> visited;
            while(head!=NULL){
                if(visited.count(head)==1){
                    return true;
                }
                visited.insert(head);
                head=head->next;
            }
            return false;
        }
    
        
       
    };
    

    题解方法二:使用快慢指针O(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) {
            if(head==NULL||head->next==NULL) return false;
            ListNode *fast=head->next,*slow=head;
            while(fast!=slow){
                if(fast==NULL||fast->next==NULL) return false;
                fast=fast->next->next;
                slow=slow->next;
            }
            return true; 
        }
    };
    
    展开全文
  • 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。 如果 pos -1,则在该链表中没有...

     

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    如果链表中存在环,则返回 true 。 否则,返回 false 。

     

    进阶:

    你能用 O(1)(即,常量)内存解决此问题吗?

     

    示例 1:

    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。
    示例 2:

    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。
    示例 3:

    输入:head = [1], pos = -1
    输出:false
    解释:链表中没有环。
     

    提示:

    链表中节点的数目范围是 [0, 104]
    -105 <= Node.val <= 105
    pos 为 -1 或者链表中的一个 有效索引 。

    空指针判断

    /**
     * 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;
            if(head == null) return false;
            while(head.next!=null&&fast.next!=null){
                fast=fast.next.next;
                head = head.next;
                if(head == null||fast ==null) break;
                if(fast.val == head.val)
                    return true;
            }
           return false; 
        }
    }

     

     

     
    展开全文
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...

    题目

    给定一个链表,判断链表中是否有环。
    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    如果链表中存在环,则返回 true 。 否则,返回 false 。
    进阶:
    你能用 O(1)(即,常量)内存解决此问题吗?
    示例 1:
    在这里插入图片描述
    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/linked-list-cycle
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题思路:快慢指针

    //解法:快慢指针法,慢指针一次走一步,快指针一次走两步,快指针先进环,慢指针后进环,当环很小,而链子很长的时候,快指针会在环里一直跑圈。
    //当慢指针进入环的时候,快指针可能在环上任意一点,这时,开始追击问题,假设快指针在X次走位后与慢指针相遇,此时快指针和慢指针相差X步,每次走位,X-1。
    //当快指针追上慢指针的时候,慢指针走了X步。(问:快指针可以一次走两步,三步吗?)
    在这里插入图片描述
    这里只有当X=0时,快慢指针相遇,说明存在环,否则在环里死循环走位。
    当快指针一次走N(N>2)步时,在X!=N 或 N 的倍数的情况下,存在无法相遇死循环的可能。

    bool hasCycle(struct ListNode *head) {
    	ListNode* fast = head;
    	ListNode* slow = head;
    	while (fast && fast->next)
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    		if (fast == slow)
    		{
    			return true;
    		}
    	}
    	return false;
    }
    
    展开全文
  • 经典双指针方法,一个指针每次向后移动两个节点,一个指针每次向后移动一个节点,如果链表,最终两个指针会碰到一起, 主要问题:有环链表,能找出环的切入口节点吗? 也利用快慢双指针,不过技巧在于,第一...
  • 首先说明一点就是如果链中存在,可能整个链是一个环,也可能链表的后面一部分形成了。如何判断链表中是否存在,经典的判断方法就是利用两个指向链表头节点的指针,同时移动,两个指针每次移动的节点数不...
  • 能否找到环的一个节点? (1)判断有 设置两个指针,快慢指针,p1,p2,p2一次走两步,p1一次走一步。如果p2走过程中到达表尾,则没有,否则p1,p2回进入,p2会追上p1。此时有。 扩展1 2个指针走步数...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 什么是链表链表是程序中最常用数据结构之一。程序处理数据,很多属于序列,将这些有顺序数据组织在一起,除了使用连续数组外,还...单向链表,是指一个节点,只能找到下一个节点,但是找不到前一个节点。...
  • 其实环形链表就是 链表的尾节点的next指针指向头节点,就跟贪吃蛇咬到自己尾巴这种造型的 有点不形象 反正就是这意思,老铁们。 咱们想想奥 如果这链表了,如果我们想遍历链表 不就是完蛋了吗,就会一直死...
  • 一、概念梳理链表是计算机科学里面应用应用最广泛数据结构之一。它是最简单数据结构之一,同时也是比较高阶数据结构(例如棧、环形缓冲和...一个单独列表元素叫做一个节点。这些节点不像数组一样都按顺序存储...
  • 因为一旦两个链表出现相交的情况,就可能发生这样的情况,程序释放了链表La的所有节点,这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了,而Lb的使用者,可能并不知道事实的真相,这会带来很大的...
  • 如题,面试时被问了好几次这个问题。我思路判断两个链表最后一个节点是否相同,面试官问我如果链表很长怎么办,求助,还有更好办法吗?
  • 只能访问该节点的话,那该节点的一个节点我们无法访问的。一般我们的思路这样的,如果我们要删除节点b,那么我们需要用a节点的next指向b节点next指向的c节点,那么就做好了删除节点的操作了,被删除的节点会被...
  • 分析问题:我们首先想到的是暴力解法, n*n复杂度,遍历一个链表的同时,再遍历另外一个链表,判断另一个链表里是否有节点是当前的节点。但是,我们再想象一下,链表交叉会什么样情况? Y型对吧?不可能X型...
  • 双向链表如果不加思考话,乍一看这就不是个环吗,但是环概念末尾指向最前端,而双向链表的是从下一个节点反向指向上一个节点,所以要记住。 ...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 环形链表

    2020-12-06 10:45:34
    给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • Leetcode No.141 环形链表

    2021-03-07 00:29:45
    给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...
  • 给定一个链表,判断链表中是否有。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表的环,我们使用整数 pos 来表示链表尾连接到链表位置(索引从 0 开始)。...

空空如也

空空如也

1 2 3 4 5 6
收藏数 118
精华内容 47
关键字:

一个节点的链表是环吗