LeetCode Hot100 刷题笔记（3）—— 链表

目录

前言

1. 相交链表

2. 反转链表

3. 回文链表

4. 环形链表

5. 环形链表 II

6. 合并两个有序链表

7. 两数相加

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

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

10. K 个一组翻转链表

11. 随机链表的复制

12. 排序链表

13. 合并 K 个升序链表

14. LRU 缓存

---

前言

一、链表：相交链表，反转链表，回文链表，环形链表，环形链表 II，合并两个有序链表，两数相加，删除链表的倒数第 N 个结点，两两交换链表中的节点，K 个一组翻转链表，随机链表的复制，排序链表，合并 K 个升序链表，LRU 缓存。(日更中...)

*** Trick：本质将链表转为list，再在list上进行操作，最后转回链表。

*** Trick 通用模版：

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution(object):def Operation(self, head):if not head:return Nonelst = []while head:lst.append(head.val)head = head.next"""系列操作"""head_new = ListNode(int(lst[0]))curr = head_newfor v in lst[1:]:curr.next = ListNode(int(v))curr = curr.nextreturn head_new

---

1. 相交链表

原题链接：160. 相交链表 - 力扣（LeetCode）

class Solution(object):def getIntersectionNode(self, headA, headB):set1 = set()while headA:set1.add(headA)headA = headA.nextwhile headB:if headB in set1:return headBheadB = headB.nextreturn None

2. 反转链表

原题链接：206. 反转链表 - 力扣（LeetCode）

class Solution(object):def reverseList(self, head):if not head:return Nonelst = []while head:lst.append(head.val)head = head.nextlst.reverse()head_new = ListNode(int(lst[0]))curr = head_newfor v in lst[1:]:curr.next = ListNode(int(v))curr = curr.nextreturn head_new

3. 回文链表

原题链接：234. 回文链表 - 力扣（LeetCode）

class Solution(object):def isPalindrome(self, head):if not head:return Nonelst = []while head:lst.append(head.val)head = head.nextif lst == lst[::-1]:return Truereturn False

4. 环形链表

原题链接：141. 环形链表 - 力扣（LeetCode）

class Solution(object):def hasCycle(self, head):if not head:return Falseset1 = set()while head:set1.add(head)head = head.nextif head in set1:return Truereturn False

5. 环形链表 II

原题链接：142. 环形链表 II - 力扣（LeetCode）

class Solution(object):def detectCycle(self, head):if not head:return Noneset1 = set()while head:set1.add(head)head = head.nextif head in set1:return headreturn None

6. 合并两个有序链表

原题链接：21. 合并两个有序链表 - 力扣（LeetCode）

class Solution(object):def mergeTwoLists(self, list1, list2):if not list1 and not list2:return Noneelif not list1:return list2elif not list2:return list1else:lst1, lst2 = [], []while list1:lst1.append(list1.val)list1 = list1.nextwhile list2:lst2.append(list2.val)list2 = list2.nextlst = lst1 + lst2lst.sort()head = ListNode(int(lst[0]))curr = headfor v in lst[1:]:curr.next = ListNode(int(v))curr = curr.nextreturn head

7. 两数相加

原题链接：2. 两数相加 - 力扣（LeetCode）

class Solution(object):def addTwoNumbers(self, l1, l2):lst1, lst2 = [], []while l1:lst1.append(l1.val)l1 = l1.nextwhile l2:lst2.append(l2.val)l2 = l2.next# s1 = ''.join(l1)# s2 = ''.join(l2)lst1.reverse()lst2.reverse()s1 = ''.join([str(i) for i in lst1])s2 = ''.join([str(i) for i in lst2])s3 = int(s1) + int(s2)lst3 = list(str(s3))lst3.reverse()head = ListNode(int(lst3[0]))curr = headfor v in lst3[1:]:curr.next = ListNode(int(v))curr = curr.nextreturn head

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

原题链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

class Solution(object):def removeNthFromEnd(self, head, n):lst = []while head:lst.append(head.val)head = head.nextdel lst[-n]if not lst:return Noneelse:head_new = ListNode(lst[0])curr = head_newfor v in lst[1:]:curr.next = ListNode(v)curr = curr.nextreturn head_new

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

原题链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

class Solution(object):def swapPairs(self, head):if not head:return Nonelst = []while head:lst.append(head.val)head = head.nextfor i in range(0, len(lst)-1, 2):lst[i], lst[i+1] = lst[i+1], lst[i]head_new = ListNode(lst[0])curr = head_newfor value in lst[1:]:curr.next = ListNode(value)curr = curr.nextreturn head_new

10. K 个一组翻转链表

原题链接：25. K 个一组翻转链表 - 力扣（LeetCode）

class Solution(object):def reverseKGroup(self, head, k):lst = []while head:lst.append(head.val)head = head.nextfor i in range(0, len(lst)-k+1, k):lst[i:i+k] = lst[i:i+k][::-1]head_new = ListNode(lst[0])curr = head_newfor v in lst[1:]:curr.next = ListNode(v)curr = curr.nextreturn head_new

11. 随机链表的复制

原题链接：138. 随机链表的复制 - 力扣（LeetCode）

class Node:def __init__(self, x, next=None, random=None):self.val = int(x)self.next = nextself.random = randomclass Solution(object):def copyRandomList(self, head):return copy.deepcopy(head)

12. 排序链表

原题链接：148. 排序链表 - 力扣（LeetCode）

class Solution(object):def sortList(self, head):if not head:return Nonelst = []while head:lst.append(head.val)head = head.nextlst.sort()head_new = ListNode(int(lst[0]))curr = head_newfor v in lst[1:]:curr.next = ListNode(int(v))curr = curr.nextreturn head_new

13. 合并 K 个升序链表

原题链接：23. 合并 K 个升序链表 - 力扣（LeetCode）

class Solution(object):def mergeKLists(self, lists):if not lists:return Nonelst1 = []for head in lists:lst2 = []while head:lst2.append(head.val)head = head.nextlst1.append(lst2)lst1 = sum(lst1, [])  if not lst1:return None      # lst1 = [[]]lst1.sort()head_new = ListNode(lst1[0])curr = head_newfor v in lst1[1:]:curr.next = ListNode(v)curr = curr.nextreturn head_new

14. LRU 缓存

原题链接：