经典面试题-环形链表 II

经典面试题-环形链表 II

经典面试题-环形链表 II

• 前言
• 142. 环形链表 II
• • 问题描述
  • 方法一
  • 方法二
• 总结

---

前言

这是一道经典的面试题来源于力扣142. 环形链表 II

---

142. 环形链表 II 问题描述

  给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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
解释：链表中没有环。

方法一

快慢指针

  和141一样，用两个指针，一个一次走一步，一个一次走两步，如果当前链表没有环的话，快指针就会一直在慢指针前面，如果有环的话，快的会先进入环，然后一直在环中转，慢的会后进入环，然后也在其中转，经过一段时间它们就会相遇。当它们相遇之后再指定一个指针指向链表头结点，依次遍历最终和慢结点相遇就是链表开始入环的第一个节点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow=head,*fast=head;//快慢指针
        while(fast!=NULL)
        {
            slow=slow->next;
            if(fast->next==NULL)
            {
                return NULL;
            }
            fast=fast->next->next;
            if(fast==slow)
            {
                ListNode* ptr=head;
                while(ptr!=slow)
                {
                    ptr=ptr->next;
                    slow=slow->next;
                }
                return ptr;
            }
        }
        return NULL;
    }
};

方法二

哈希表
  这理解起来就更简单了，将遍历的结点都加到表中，再与新加入的结点对比，相同就是链表开始入环的第一个节点。如果没环则遍历到指向空就结束。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        unordered_set visited;
        while(head!=NULL)
        {
            if(visited.count(head))
            {
                return head;
            }
            visited.insert(head);
            head=head->next;
        }
        return NULL;
    }
};

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！