-
请问单链表的环一定是从尾节点指向链表的其它节点吗?
2016-08-27 14:00:06比如一个单链表是a->b->c->d->e->f,如果从d指向b,构成的环是否有意义呢? -
判断两个单链表是否相交,若相交,求节点(链表不带环)
2018-09-18 20:18:53先判断链表是否相交,我们可以运用两个链表相交后就变成了一条链表这个特性来判断,因为如果两条链表相交,那么这两条链表的最后一个节点一定是同一个节点,否则不可能相交 //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; }
-
141. 环形链表: 给定一个链表,判断链表中是否有环。
2021-03-02 15:17:25给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 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; } };
-
leetcode-给定一个链表,判断链表中是否有环。
2020-12-27 15:53:00如果链表中有某个节点,可以通过连续跟踪 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; } }
-
letcode题目:141. 环形链表(判断一个链表中是否带环)
2020-12-28 18:21:32给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 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; }
-
5分钟一个算法编程小点:链表判断是否有环,并且给出环的位置
2020-10-11 14:22:41经典的双指针方法,一个指针每次向后移动两个节点,一个指针每次向后移动一个节点,如果链表有环,最终两个指针会碰到一起, 主要问题:有环链表,能找出环的切入口节点吗? 也是利用快慢双指针,不过技巧在于,第一... -
-
判断链表中是否存在环的方法及证明
2021-01-20 11:01:10首先说明一点就是如果链中存在环,可能整个链是一个环,也可能是该链表的后面一部分形成了环。如何判断链表中是否存在环,经典的判断方法就是利用两个指向链表头节点的指针,同时移动,两个指针每次移动的节点数是不... -
判断链表有环及其扩展问题
2015-04-16 09:09:14能否找到环的第一个节点? (1)判断有环 设置两个指针,快慢指针,p1,p2,p2一次走两步,p1一次走一步。如果p2走的过程中到达表尾,则没有环,否则p1,p2回进入环,p2会追上p1。此时有环。 扩展1 2个指针走的步数... -
11、leetcode环形链表、最后一个单词的长度
2020-09-22 21:55:21给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
是单向链表吗_不找对象,怎么实现单向链表(1)
2021-01-14 10:35:01什么是链表链表是程序中最常用的数据结构之一。程序处理的数据,很多属于序列,将这些有顺序的数据组织在一起,除了使用连续的数组外,还...单向链表,是指一个节点,只能找到下一个节点,但是找不到前一个节点。... -
从环形链表来看约瑟夫环的问题
2019-10-11 14:11:19其实环形链表就是 链表的尾节点的next指针指向头节点,就跟贪吃蛇咬到自己尾巴这种造型是的 有点不形象 反正就是这个意思,老铁们。 咱们想想奥 如果这链表有环了,如果我们想遍历链表 不就是完蛋了吗,就会一直死... -
python链表有用吗_用python实现链表
2021-01-30 05:30:56一、概念梳理链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧、环形缓冲和...一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储... -
如何判断两个链表相交及找到第一个相交点
2017-11-01 20:35:29这是因为一旦两个链表出现相交的情况,就可能发生这样的情况,程序释放了链表La的所有节点,这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了,而Lb的使用者,可能并不知道事实的真相,这会带来很大的... -
不需要遍历判断两个链表是否相交?(没有环)
2014-10-20 13:43:23如题,面试时被问了好几次这个问题。我的思路是判断两个链表最后一个节点是否相同,面试官问我如果链表很长怎么办,求助,还有更好的办法吗? -
python-链表练习,还不做做吗?
2020-09-01 21:56:12只能访问该节点的话,那该节点的上一个节点我们是无法访问的。一般我们的思路是这样的,如果我们要删除节点b,那么我们需要用a节点的next指向b节点next指向的c节点,那么就做好了删除节点的操作了,被删除的节点会被... -
算法与数据结构面试分享(十五)判断两个链表是否有交叉(单链表,不含环)
2018-04-04 23:01:40分析问题:我们首先想到的是暴力解法, n*n的复杂度,遍历一个链表的同时,再遍历另外一个链表,判断另一个链表里是否有节点是当前的节点。但是,我们再想象一下,链表交叉会是什么样的情况? Y型对吧?不可能是X型... -
双向链表不是环形链表
2019-10-09 07:43:58双向链表如果不加思考的话,乍一看这就不是个环吗,但是环的概念是从的末尾指向最前端,而双向链表的是从下一个节点反向指向上一个节点,所以要记住。 ... -
每日一题:环形链表(简单)
2020-10-09 19:30:41给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
10.9每日一题 141. 环形链表
2020-10-09 09:48:53给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
环形链表
2020-12-06 10:45:34给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
Leetcode No.141 环形链表
2021-03-07 00:29:45给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)... -
2020_10_9 每日一题 环形链表
2020-10-09 08:36:16给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
【一天一大 lee】环形链表 (难度:简单) - Day20201009
2020-10-09 18:00:46给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
LeetCode第141题 环形链表的判断
2021-02-07 11:19:39给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
141. Linked List Cycle 环形链表
2020-10-09 07:48:45给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
数据结构之链表:141. 环形链表
2020-10-01 09:42:32给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。... -
LeetCode 141 环形链表 HERODING的LeetCode之路
2020-10-09 07:32:54给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。...