LeetCode142. 环形链表 II(C++俩种解法)

举报
莫浅子 发表于 2022/12/21 22:14:47 2022/12/21
【摘要】 ​ 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际...

 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

不允许修改 链表。

示例 1:

编辑

 输入:head = [3,2,0,-4], pos = 1

 输出:返回索引为 1 的链表节点

 解释:链表中有一个环,其尾部连接到第二个节点

 示例 2:

编辑

 输入:head = [1,2], pos = 0

 输出:返回索引为 0 的链表节点

 解释:链表中有一个环,其尾部连接到第一个节点。

示例3: 


编辑

 输入:head = [1], pos = -1

 输出:返回 null

 解释:链表中没有环。

解法1 

思路:

使用set求环起始结点

1、遍历链表,将链表结点对应指针(地址),插入set。

2、在遍历时插入结点前,需要在set中查找,第一个在set中发现的结点地址,即链表环的起点

代码如下 


class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode *> note_set;
        while(head)
        {   
            if(note_set.find(head) != note_set.end())
            return head;
            note_set.insert(head);
            head = head->next;
        }
        return NULL;
        
    }
};


解法2 

思路:

使用快慢指针解题

快指针每次走俩步,慢指针每次走一步。如果是环,必会相遇,所以第一步知道相遇点的话即为环,且这个环的点与head到初始循环的点的路程是一样长的,他俩每次走一步,相遇的点即为起始循环的点

编辑

编辑

结论:head与meet同时出发,相遇即环的起点 

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *meet = NULL;
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
            if(!fast) return NULL;
            fast = fast -> next;
            if(slow == fast)
            {
                meet = fast;
                break;
            }
        }
        if(meet == NULL){
             return NULL;
        }
        while(head && meet){
            if(head == meet)
              return head;
            head = head->next;
            meet = meet->next;
        }
    
        return NULL;
        
    }
};


 



【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。