【剑指Offer】55链表中环的入口结点

迈不过友情╰ 2022-04-21 23:36 165阅读 0赞

## 题目描述 ##

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

时间限制：1秒；空间限制：32768K；本题知识点：链表

## 解题思路 ##

### 思路一 ###

用一个list记录链表结点，空间复杂度大。

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            # write code here
            l = [] #记录节点
            if pHead == None:
                return None
            while pHead.next != None:
                for i in range(len(l)):
                    if pHead==l[i]:
                        return pHead
                l.append(pHead)
                pHead = pHead.next
            return None

### 思路二 ###

*  第一步，找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到slow==fast找到在环中的相汇点。
 *  第二步，找环的入口。当slow==fast时，让其中一个指针指向链表头部，另一个位置不变，fast和slow每次都走一步直到再次slow==fast，此时指向的是环的入口。

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            # write code here
            if pHead == None:
                return "null"
            # 找环中相汇点
            if pHead.next!=None and pHead.next.next!=None: #先跑一次以满足循环条件
                fast = pHead.next.next
                slow = pHead.next
            else:
                return None
            while fast != slow:
                if fast.next!=None or fast.next.next!=None:
                    fast = fast.next.next
                    slow = slow.next
                else:
                    return None
            # 找环的入口
            fast = pHead
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return slow