1、两个链表的公共节点
原题地址：剑指 Offer 52. 两个链表的第一个公共节点
解题思路：
- 哈希表法 时间O(n+m) 空间O(n+m)
- 双指针遍历法 时间O(n+m) 空间O(1)
（1）哈希法：
两次遍历：
- 第一次遍历list1，存储list1 的全部节点到set
- 第二次遍历list2，对比set集合中的就
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
myset = set()
cura, curb = headA, headB
while cura:
myset.add(cura)
cura = cura.next
while curb:
if curb in myset:
return curb
curb = curb.next
return
（2）双指针遍历法
利用双指针进行两个节点的遍历，如果两个指针相遇则证明当前两个链表有公共节点
"""
输入两个链表，找出它们的第一个公共节点
"""
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cur_a, cur_b = headA, headB
while cur_a != cur_b:
cur_a = cur_a.next if cur_a else headB
cur_b = cur_b.next if cur_b else headA
return cur_a
2、环形链表
2-1 判断一个链表是否是环形链表
原题地址：https://leetcode-cn.com/problems/linked-list-cycle/
解题思路：
-
使用set ：通用思路，没什么亮点主要是空间复杂度比较高
-
快慢指针：在空间上进行了优化
"""
使用set
时间复杂度：O(n)
空间复杂度：O(n)
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
myset = set()
cur = head
while cur:
if cur in myset:
return True
myset.add(cur)
cur = cur.next
return False
"""
快慢指针法
时间复杂度：O(n)
空间复杂度：O(1)
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next: return False # 保证至少有两个值
slow = head
fast = head.next
while True:
if slow == fast: return True
# 出现 null 则证明不是环形链表
if not slow or not slow.next or not fast.next or not fast.next.next: return False
slow = slow.next
fast = fast.next.next
2-2 如果一个链表是环形链表，求入环节点
原题地址：https://leetcode-cn.com/problems/linked-list-cycle-ii/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
假设快慢指针在紫点处相遇
假设fast走了n圈，则
fast走的路程：len_fast = a+n(b+c)+b ，而且fast走的路程是slow的二倍，且len_slow = a+b
则有：a+n(b+c) +b= 2(a+b)，化简得 a=c+(n-1)(b+c)
含义为：当fast保证和slow相同速度(每次走1步)重新从a开头走到相交点的话，slow需要走相遇点走到c，并且需要多走n-1圈，但是最后其能保证fast和slow能在交点相遇
