142. 环形链表 II
https://leetcode.cn/problems/linked-list-cycle-ii/
哈希法：
我的思路：
- 维护一个集合存储走过的节点，遇到走过的节点，进行一次判断，如果该节点在集合里面，则直接返回该节点。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
dic = set()
while head:
if head not in dic:
dic.add(head)
else:
return head
head = head.next
return
非常简单的思路，但为此做出的牺牲就是空间消耗
时间复杂度为：O(n)
空间复杂度为：O(n)
双指针：
大佬思路：
https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
ans = head
while ans != slow:
slow = slow.next
ans = ans.next
return ans
return
这是一道数学题，认真看完，会有收获，遇到链表题都可以尝试双指针。
时间复杂度：O(n)，第二次相遇中，慢指针须走步数 a < a + ba<a+b；第一次相遇中，慢指针须走步数 a + b - x < a + ba+b−x<a+b，其中 xx 为双指针重合点与环入口距离；因此总体为线性复杂度；
空间复杂度：O(1)
PS：哈希法比双指针的快一点点
92. 反转链表 II
https://leetcode.cn/problems/reverse-linked-list-ii/
思路：
- 局部反转列表，由于要返回整个列表，需要构建头结点dummy_node
- 采用局部断链、接链的方法，一步一步反转，每一次反转2个节点，需要反转right-left次
- 如何反转2个节点：画图，自己断链，注意断链的顺序（可以看为两步）
- 第一步，cur和next交换位置
- 第二步，把next进节点进行头插法
- 注意：pre节点始终不变，cur节点也始终不变
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
pre = dummy = ListNode(-1)
dummy.next = head
for _ in range(left-1): # 进行left-1次后移，直到pre指向需要反转的节点的前一个节点
pre = pre.next
cur = pre.next
for _ in range(right-left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummy.next
# 也可以写成
next = cur.next
cur.next, next.next, pre.next = next.next, pre.next, next
# 花里胡哨的方式，不推荐
138. 复制带随机指针的链表
https://leetcode.cn/problems/copy-list-with-random-pointer/
解法0 ：
深拷贝
class Solution(object):
def copyRandomList(self, head):
return copy.deepcopy(head)
解法一（连接法）：
连接法是将原链表和新链表连在一起，即 1 -> 1' -> 2 -> 2' -> 3 -> 3'，新链表节点始终在原链表节点的后面 构建连接的链表 复制random节点，如果有random，就复制（这里不需要判断cur.next）是否存在，因为肯定存在 最后一步，将链表断开，采用了头结点的方式，画个图断个链就行了 important！！！ 为什么采用构建链表的方法？？？因为不确定random到底指向哪里，所以要事先构建新链表的全貌！！！
class Solution(object):
def copyRandomList(self, head):
if not head: return
# 连接法
cur = head
while cur:
new_node = Node(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
# 复制random节点
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 利用头结点断开链接
p = dummy = Node(-1)
cur = head
while cur:
p.next = cur.next
cur.next = p.next.next
p = p.next
cur = cur.next
return dummy.next
解法二（哈希法）：
维护一个字典，来储存新链表，key为旧链表节点，value为新链表节点 第一步，构建链表，存入dic 第二步，遍历原列表，复制next节点和random节点 由于要返回整个链表，毫无疑问是采用头结点的方式返回
class Solution(object):
def copyRandomList(self, head):
if not head: return
dic = {}
cur = head
while cur:
new_node = Node(cur.val)
dic[cur] = new_node
cur = cur.next
cur = head
while cur:
if cur.next:
dic[cur].next = dic[cur.next]
if cur.random:
dic[cur].random = dic[cur.random]
cur = cur.next
return dic[head]