141&142 环形链表

时间：2020-07-25 20:19:43 阅读：42 评论：0 收藏：0 [点我收藏+]

141.环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

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

思路1：

用 set 存储每个节点的位置，判断是否有重复的节点，重复说明有环，时间复杂度 o(n)，空间复杂度 o(n)

代码

/**
 * 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) {
        unordered_set<ListNode*> st;
        ListNode *p = head;
        if(p==NULL||p->next==NULL)
        {
            return 0;
        }
        st.insert(p);
        while(p!=NULL)
        {
            p = p->next;
            unordered_set<ListNode*>::iterator it = st.find(p);
            if(it!=st.end())
            {
                return 1;
            }
            else
            {
                st.insert(p);
            }
        }
        return 0;
        
    }
};

思路2：

快慢指针，开始快= 慢，每次移动快+2，慢+1，有环快慢相遇，否则快先遇到NULL，时间复杂度o(n), 空间复杂度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) {
        ListNode *fast = head, *slow = head;
        while(fast!=NULL&&fast->next!=NULL)
        {
           fast = fast->next->next;
           slow = slow->next;
           if(fast == slow)
           return 1;
        }
        return 0;
        
    }
};

142.环形链表2

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

思路1：

用 set 存储每个节点的位置，判断是否有重复的节点，重复说明有环，且重复的节点即为环的入口。时间复杂度 o(n)，空间复杂度 o(n)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
     unordered_set<ListNode*> st;
        ListNode *p = head;
        if(p==NULL||p->next==NULL)
        {
            return NULL;
        }
        st.insert(p);
        while(p!=NULL)
        {
            p = p->next;
            unordered_set<ListNode*>::iterator it = st.find(p);
            if(it!=st.end())
            {
                return *it;
            }
            else
            {
                st.insert(p);
            }
        }
        return NULL;
    }
};

思路2：

快慢指针找到环的入口，开始快= 慢，每次移动快+2，慢+1，无环快先遇到NULL，有环快慢相遇，相遇之后，慢= head，快+1，慢+1，再次快慢相遇的点为环的入口。时间复杂度o(n), 空间复杂度o(1)。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                slow = head;
                while(fast!=slow)
                {
                    fast= fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return NULL;
        
    }
};

141&142 环形链表

原文：https://www.cnblogs.com/jessica216/p/13376015.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)