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 缓存
原题链接: