55. 链表中环的入口结点
55. 链表中环的入口结点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路
链表有环的意思就是，最后一个节点的next指向了前面的某个节点，链表没有None的链表尾部出口。
思路一：
引入辅助空间，用一个列表保存已经遍历过的节点，如果再次出现，则说明这个节点就是链表环的入口节点。
思路二：
设：链表长度为N，链表环长度为m
1.用两个指针来遍历这个链表，一个每次走一步，一个每次走两步，两个指针会在链表环中的节点相遇。
2.然后继续遍历其中的一个，步长为1，可以计算出链表环中节点的个数m。
3.重新遍历链表，一个指针从头结点0开始(距链表环入口节点N-m)，另一个节点从节点m开始(距链表环入口节点也是N-m)，两个节点会在链表环入口节点处相遇，于是得到链表环入口节点。
代码实现
思路一：
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
hashList= []
headNode = pHead
while headNode:
if(headNode == None):
return None
if(headNode in hashList):
return headNode
else:
hashList.append(headNode)
headNode = headNode.next思路二：
# -*- 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 not pHead or not pHead.next or not pHead.next.next:
return None
# 用两个指针来遍历这个链表，一个每次走一步，一个每次走两步，两个指针会在链表环中的节点相遇。
headSlow = pHead
headFast = pHead.next
while (headSlow != headFast):
if headSlow.next == None or headFast.next.next == None:
return None
headSlow = headSlow.next
headFast = headFast.next.next
# 此时headSlow = headFast 在环中某节点相遇
# 继续遍历其中的一个，步长为1，遍历headFast
count = 1
headFast = headFast.next
while(headSlow != headFast):
headFast = headFast.next
count += 1
# count为链表环中节点的个数
# 重新遍历链表，一个指针从头结点0开始(距链表环节点N-m)，另一个节点从节点m开始(距链表环入口节点是N-m)
# 两个节点会在链表环入口节点处相遇，于是得到链表环入口节点。
headSlow = pHead
headFast = pHead
for i in range(count):
headFast = headFast.next
while(headSlow != headFast):
headSlow = headSlow.next
headFast = headFast.next
return headSlow
