LeetCode 142. 环形链表 II(Linked Lis
LeetCode.jpg
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 1.png
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 2.png
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
示例 3.png
切题
一、Clarification
注意链表位置索引从0开始
二、Possible Solution
1、哈希表
set存储记录所有节点，如果下一节点在set中有那么此节点就是入环的第一个节点；如果直到链表结尾都没有重复节点，表示无环，注意最后的None要提前放入set中。时间复杂度O(n)，空间复杂度O(n)
2、快慢指针
参考 141通过快慢指针，slow每次移动1，fast每次移动2，可以找到他们相遇时的节点假设为meetnode，入环的第一个节点假设为firstnode,如下图。由于slow每次移动1，fast每次移动2，可知道head->firstnode->meetnode的节点个数 = meetnode->firstnode->meetnode的节点个数，除去中间相同的一部分head->firstnode的节点个数 = meetnode->firstnode的节点个数。 时间复杂度O(n)，空间复杂度O(1)
image.png
Python3 实现
哈希表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# @author:leacoder
# @des: 哈希表 环形链表 II
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
nodes = set()
nodes.add(None)
cur = head
while cur not in nodes:
nodes.add(cur)
cur = cur.next
return cur
快慢指针
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# @author:leacoder
# @des: 快慢指针 环形链表 II
class Solution(object):
def getmeetnode(self,head):
fast = slow = head
while slow and fast and fast.next:
slow = slow.next #慢指针 每次移一步
fast = fast.next.next #快指针 每次移二步
if slow == fast:
return slow # 找出相遇节点
return None # 没有表示没有成环，返回None
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
meetnode = self.getmeetnode(head) # 找到 相遇时的节点meetnode
if meetnode is None: # 如果为None 表示不成环
return None
# 成环 由于 head->firstnode的节点个数 = meetnode->firstnode的节点个数
cur1 ,cur2 = head,meetnode
while cur1!=cur2:
cur1,cur2 = cur1.next,cur2.next
return cur1
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
