当前位置: 首页 > news >正文

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 缓存

原题链接:


http://www.mrgr.cn/news/97391.html

相关文章:

  • spring boot 整合redis
  • MySQL窗口函数学习
  • AI爬虫?爬!
  • [ctfshow web入门] 零基础版题解 目录(持续更新中)
  • Nginx-keepalived-高可用
  • Nginx 负载均衡案例配置
  • RAG 架构地基工程-Retrieval 模块的系统设计分享
  • 深度学习环境安装
  • 蓝桥杯嵌入式第十四届模拟二(PWM、USART)
  • K8S学习之基础七十四:部署在线书店bookinfo
  • Nginx 配置文件解析
  • 如何让 -webkit-slider-thumb 生效
  • c++项目 网络聊天服务器 实现;QPS测试
  • 【HFP】蓝牙HFP应用层核心技术研究
  • 算法基础—前缀和
  • 深入解析多功能模糊搜索:构建高效灵活的JavaScript搜索工具析
  • Java 集合框架与 Stream 流深入剖析(重点详细讲解)
  • ffmpeg视频转码相关
  • Python星球日记 - 第5天:循环结构
  • 个人博客系统——测试报告