一、141. 环形链表
简单
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
在本题中使用快慢指针：
若是链表无环，那么 fast 指针会先指向 Null。
若是链表有环，fast 和 slow 迟早会在环中相遇。
class Solution:
def hasCycle(self, head):
#如果空链表或者只有一个节点。无环
if not head or head.next == None:
return False
#初始化快慢指针
slow=head
fast=head
#如果不存在环，肯定fast指向null
#细节：fast每次走2步，所以要确定fast和fast.next不为空，不然指向报错
while fast and fast.next:
#快指针移动2步，慢指针移动1位
fast=fast.next.next
slow=slow.next
#快慢指针相遇，有环
if fast == slow:
return True
return False
二、876. 链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
解题思路：
考虑借助快慢双指针 fast, slow ，「快指针 fast」每轮走 2 步，「慢指针 slow」每轮走 1 步。fast 的步数恒为 slow 的 2 倍，因此当快指针遍历完链表时，慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点，因此需要分两种情况考虑：
链表长度为奇数： 当 fast 走到链表「尾节点」时，slow 正好走到「中间节点」。
链表长度为偶数： 当 fast 走到「null」时（越过「尾节点」后），slow 正好走到「第二个中间节点」。
总结以上规律，应在当 fast 遇到尾节点或越过尾节点时跳出循环，并返回 slow 即可。
执行步骤如下
class Solution:
def middleNode(self,head):
fast=slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
return slow
三、面试题 02.01. 移除重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？
题目要求删除链表中的「重复节点」，并保留「最开始出现的节点」。考虑遍历链表，借助一个「哈希表 Set 」记录遇到的节点值，在遍历过程中判断：
若当前节点在 Set 中，代表是「重复节点」，则删除之；
若当前节点不在 Set 中，代表此节点第一次遇到，则将此「节点值」加入到 Set 中；
class Solution:
def removeDuplicateNodes(head:ListNode):
pre=None
cur=head
v=set()
while cur:
if cur.val in v:
pre.next=cur.next
else:
v.add(cur.val)
pre=cur
cur=cur.next
return head
