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
解释：链表中没有环。
思路：
解法1
很容易就会想到将遍历到的结点都存储起来，这样如果有环的话，那么环里的结点会遍历多次
代码：
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 选择用集合存储，这样查找的效率比较高
seen = set()
cur = head
while cur:
# 如果发现结点在集合中，就说明有环的存在
if cur in seen: return True
seen.add(cur)
cur = cur.next
return False
解法2：
遍历链表，一般可以采用快慢指针来解决，如果没有环，那么快指针会走到链表的尾结点，如果有环，快慢指针会在环的某个点相遇。
代码：
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next: return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 如果快慢结点相遇了，就说明存在环
if slow == fast: return True
return False
142、环形链表2
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
思路
这道题和判断链表有无环很像，这里可以在判断的基础上进行修改。
解法1：
如果有环，那么第一个出现重复的结点，就是环的入口点了。
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 选择用集合存储，这样查找的效率比较高
seen = set()
cur = head
while cur:
# 第一个出现重复的点，就是环的入口点
if cur in seen: return cur
seen.add(cur)
cur = cur.next
return None
解法2：
快慢指针可以找到是否有环，但是快慢指针相遇的位置不一定是环的入口，可以想到此时慢节点移动的距离是，环入口到头结点的距离+n倍环的距离
那么如果此时再有一个结点，从头结点出发，那么该节点与慢节点相遇应该就是环的入口结点了。（详细推导可以见leetcode官方）
代码：
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next: return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
return None
160、相交链表
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
思路：
解法1
采用hash的方式来存储已经遍历的结点，当遍历出现已经存储的结点，该结点就是相交的结点，否则不相交
代码：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB: return None
seen = set()
cur = headA
while cur:
seen.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in seen: return cur
cur = cur.next
return None
解法2：
如果两个单链表相交，那么同时移动两个链表，要么在相交点相遇，要么一前一后到达终点，这个时候只需要将遍历的结点对调，那么再次遍历则在相交点出相交
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB: return None
curA = headA
curB = headB
while curA != curB:
# 如果A链表遍历到终点，切换到链表B上遍历
curA = curA.next if curA else headB
# 如果B链表遍历到终点，切换到链表A上遍历
curB = curB.next if curB else headA
return curA
网友评论