首页 > 其他 > 详细

剑指offer | 链表中环的入口结点 | 18

时间:2021-01-21 09:26:33      阅读:33      评论:0      收藏:0      [点我收藏+]


技术分享图片

思路分析

如果没有环,非常简单,遍历一次如果到NULL那么就结束,也就证明这个链表没有环.
(这是最关键的思路,如果有环的话是见不到NULL的)

哈希表

哈希表就是遍历一次,每次遍历都把遍历过的结点放入集合中,如果下一个遍历的点存在,那么这个点就是入口结点.

cpp

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead)return NULL;
        unordered_set<ListNode*> S;
        for(auto p = pHead;p;p=p->next){
            if(S.count(p)==0)
                 S.insert(p);
            else
                return p;
            
        }
        return NULL;
    }
};

python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        S = set()
        p = pHead
        while p:
            if p not in S:
                S.add(p)
            else: return p
            p = p.next
        return None

双指针

双指针的思路:
两个指针fastslow,fast步长为2,slow步长为1.
如果fast遇到了NULL,那么证明没有环.
否则, 第一次fastslow相遇的时候,slow在原地不动,fast回到头节点处,两指针第二次相遇的时候就是环的入口结点.

这个题难就难在证明过程,这个证明过程要熟悉.

技术分享图片

cpp

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        auto fast=pHead,slow=pHead;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)break;
        }
        if(!fast || !fast->next)return NULL; // 无环
        fast = pHead;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        fast=pHead
        slow=pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast==slow:break
        if not fast or not fast.next:return None
        fast = pHead
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

剑指offer | 链表中环的入口结点 | 18

原文:https://www.cnblogs.com/Rowry/p/14305774.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!