Leetcode Hot100之链表

1.相交链表

• 解题思路
  快慢指针：分别求出两个链表的长度n1和n2，在长度较长的那个链表上，快指针先走n2 - n1，慢指针再出发，最后能相遇则链表相交
  时间复杂度O(m+n)，空间复杂度O(1)
• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:if not headA or not headB:return Nonel_a = 0l_b = 0node = headAwhile node:l_a += 1node = node.nextnode = headBwhile node:l_b += 1node = node.nextnode1 = headA node2 = headBif l_b > l_a:l_a, l_b = l_b, l_anode1, node2, = node2, node1for _ in range(l_a - l_b):node1 = node1.nextwhile node1 and node2:if node1 == node2:return node1node1 = node1.nextnode2 = node2.nextreturn None
  

2.翻转链表

• 解题思路
  最基本的题目，一定要掌握。prev初始化成None，不需要dummy_head
  时间复杂度O（N），空间复杂度O（1）
• 代码

  class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head:return head# prev直接初始化成None就好prev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn prev
  

3.回文链表

• 解题思路
  查找中间链表，然后翻转后半段，接着使用双指针比较判断即可
  时间复杂度O（N），空间复杂度O（1）
• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:def reverse(head):if not head:return headprev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn previf not head:return Falseif not head.next:return Trueslow = headfast = head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nexthead2 = reverse(slow.next)node_1 = headnode_2 = head2while node_1 and node_2:if node_1.val != node_2.val:return Falsenode_1 = node_1.nextnode_2 = node_2.nextreturn True
  

4. 环形链表

• 题目描述
  判断链表是否有环
• 解题思路
  快慢指针，快指针一次走一步，慢指针一次走两步，如果有环的话，他们一定在环中相遇。类比于操场跑圈的套圈，对于slow来说，fast是一个节点一个节点的靠近slow的
  时间复杂度：O(N)，
  空间复杂度：O(1)。
• 代码

  class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:if not head or not head.next:return Falsefast = slow = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False
  

5. 环形链表2

• 题目描述
  如果链表有环需要返回入环的节点，无环返回None
• 解题思路
  图片来自代码随想录；查找是否有环和上一题目一样，使用快慢指针，如果有环，那么他们一定在环内相遇。如下图所示，慢指针走过的路程是x + y，快指针走过的路程是 x + y + (y + z) * n，又因为快指针走的路程是慢指针的两倍，因此有x + y + (y + z) * n = 2* (x + y), 也就是(y + z) * n = x + y, 也就是(y+z)*(n-1) + z = x，那么如果两个节点分别从头结点和相遇节点出发，一定可以在入口节点处相遇；
  时间复杂度：O(N)，
  空间复杂度：O(1)。
• 代码

  class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return Noneslow = fast = headhas_cycle = Falsewhile fast and fast.next:slow = slow.nextfast = fast.next.nextif fast == slow:has_cycle = Truebreakif not has_cycle:return Nonenode1 = headnode2 = slowwhile node1 != node2:node1 = node1.nextnode2 = node2.nextreturn node1
  

6. 合并两个有序链表

• 解题思路
  是链表排序和合并K个有序链表等题目要用的基本模块
  时间复杂度O(n+m)， 空间复杂度O(n+m)
• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:if not list1:return list2if not list2:return list1head = ListNode()cur = headnode1 = list1node2 = list2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.next
  

7. 两数相加

• 题目描述
  

• 解题思路
  注意考虑进位、两个数字位数不同的情况
  时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
  空间复杂度：O(1)。注意返回值不计入空间复杂度。

• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:if not l1:return l2if not l2:return l1prev = 0n1 = n2 = 0new_head = ListNode()node1 = l1node2 = l2cur = new_headwhile node1 or node2:n1 = node1.val if node1 else 0n2 = node2.val if node2 else 0s = n1 + n2 + prevnode = ListNode(s % 10)prev = s // 10cur.next = nodecur = cur.nextif node1:node1 = node1.nextif node2:node2 = node2.nextif prev != 0:node = ListNode(prev)cur.next = nodereturn new_head.next
  

8. 删除链表的倒数第N个节点

• 解题思路
  快慢指针，快指针先走N，然后快慢一起走，当快指针走到末尾时，慢指针指向的就是要删除的节点
• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:if not head:return Nonenew_head = ListNode(0, head)prev = new_headslow = fast = headfor i in range(n):if not fast:raise ValueError("n must greter than length of list")fast = fast.nextwhile fast:prev = slowslow = slow.nextfast = fast.nextprev.next = slow.nextreturn new_head.next
  

9. 两两交换链表中的节点

• 题目描述
  给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
• 解题思路
  模拟两两交换的过程即可
• 代码

  class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head:return headnew_head = ListNode(next=head)cur = headprev = new_headwhile cur and cur.next:next = cur.nextcur.next = next.nextnext.next = curprev.next = nextprev = curcur = prev.nextreturn new_head.next
  

10. k个一组翻转链表

• 题目描述
  给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

  k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

• 解题思路
  将前k个节点切断成一个链表，进行翻转，并递归对剩下的链表进行‘k个一组翻转链表’操作，再将两个链表连起来，即可

• 代码

  class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:def reverse(head):if not head:return headprev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn previf not head:return headl = 0node = headwhile node:l += 1node = node.nextif l < k:return headnode = headfor i in range(k - 1):node = node.nextnew_head = node.nextnode.next = Nonereverse_head = reverse(head)head.next = self.reverseKGroup(new_head, k)return reverse_head
  

11. 随机链表的复制

• 解题思路
  第一遍循环，复制每个节点，并把他们通过next连接成一个普通的链表，同时构建哈希表，哈希表的key是旧的节点，value是复制的节点；
  第二遍循环，通过哈希表完成random的指定，注意random可能是空的
  时间复杂度O(N), 空间复杂度O(N)
• 代码

  class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head:return headdic = {}node = headnew_head = Node(0)prev = new_headwhile node:new_node = Node(x=node.val)prev.next = new_nodedic[node] = new_nodeprev = new_nodenode = node.nextnode = headwhile node:# 一定要注意原始节点的random是不是空的if node.random:dic[node].random = dic[node.random]node = node.nextreturn new_head.next
  

12. 排序链表

• 题目描述

• 解题思路
  解题思路：归并排序的思想，找到中间节点，然后分别对左右两边进行排序，最后合并左右两边的有序链表。
  这道题目的关键：1. 找到链表的中间节点：用快慢指针实现，慢指针一次走一步，快指针一次走两步，当快指针走到末尾时，慢指针指向的就是中间节点（不用求出链表长度再计算中间节点的位置）；2.将链表从中间节点切断成两个链表；3. 合并两个有序链表。
  时间复杂度：O(nlogn)，其中 n 是链表的长度。
  空间复杂度：O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

• 代码

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head = ListNode()cur = headnode1 = l1node2 = l2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.nextif not head or not head.next:return head# 找到中间节点的方法：快慢指针slow = headfast = head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nextnode1 = headnode2 = slow.next# 从中间断开链表slow.next = Nonehead1 = self.sortList(node1)head2 = self.sortList(node2)return merge(head1, head2)
  

13. 合并k个升序链表

• 题目描述
  给你一个链表数组，每个链表都已经按升序排列。
  请你将所有链表合并到一个升序链表中，返回合并后的链表。
• 解题思路
  分治，通过递归两两合并，其中会用到合并两个有序链表这个函数，在上一个题目排序链表中也用到了，因此这个模块函数要掌握好；
• 代码

  class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head = ListNode()cur = headnode1 = l1node2 = l2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.nextn = len(lists)if n == 0:return Noneif len(lists) == 1:return lists[0]mid = n // 2head1 = self.mergeKLists(lists[: mid])head2 = self.mergeKLists(lists[mid :])return merge(head1, head2)
  

13 LRU

• 题目描述
  请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
  实现 LRUCache 类：
  LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
• 解题思路
  哈希表 + 双向链表。哈希表用于快速查找节点，双向链表用于存储使用情况，最近被使用的节点被放在双向链表的后端
  时间复杂度： O(1)， 空间复杂度：O(capacity)。
  注意python的字典删除元素的方法是：pop(key[,default])
  删除字典给定键 key 所对应的值，返回值为被删除的值。key值必须给出。 否则，返回default值。
• 代码

  class BiNode:def __init__(self, val=0, next=None, prev=None, key=None):self.val = valself.next = nextself.prev = prevself.key = keyclass LRUCache:def __init__(self, n):self.n = nself.dic = {}self.head = BiNode()self.tail = BiNode()self.head.next = self.tailself.tail.prev = self.headdef add_node_to_tail(self, node):self.tail.prev.next = nodenode.prev = self.tail.prevnode.next = self.tailself.tail.prev = nodedef rm_node(self, node):prev = node.prevnex = node.nextprev.next = nexnex.prev = prevdef get(self, key):if key in self.dic:self.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])return self.dic[key].valelse:return -1def put(self, key, value):if key in self.dic:self.dic[key].val = valueself.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])else:if len(self.dic) == self.n:to_delete = self.head.nextself.rm_node(to_delete)self.dic.pop(to_delete.key)new_node = BiNode()new_node.val = valuenew_node.key = keyself.dic[key] = new_nodeself.add_node_to_tail(new_node)# Your LRUCache object will be instantiated and called as such:
  # obj = LRUCache(capacity)
  # param_1 = obj.get(key)
  # obj.put(key,value)
  

总结

对于链表题目，主要的解题思路有：快慢指针、翻转链表（局部）、合并有序链表、查找中间位置的链表节点、将长链表分解切断成小的链表（分治）。
需要熟练掌握的模块：翻转链表、合并有序链表、查找中间位置的链表节点
查找中间位置的链表节点，使用快慢指针：

slow = head
fast = head.next
while fast and fast.next:slow = slow.nextfast = fast.next.next