【python】链表基础

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]