算法练习--leetcode 链表

news/2024/12/22 16:25:29/

文章目录

  • 合并两个有序链表
  • 删除排序链表中的重复元素 1
  • 删除排序链表中的重复元素 2
  • 环形链表1
  • 环形链表2
  • 相交链表
  • 反转链表

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
在这里插入图片描述

输入： l 1 {l1} l1 = [1,2,4], l 2 {l2 } l2= [1,3,4]
输出：[1,1,2,3,4,4]   以列表 表示每个节点的value
 
示例 2：
输入： l 1 {l1} l1 = [], l 2 {l2} l2 = []
输出：[]   表示没有节点 None

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]  表示有一个value为0的节点

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 升序排列

python实现：双指针

# 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]:   # ListNode or Noneif not list1 and not list2:return None  # [] 代表空节点elif not list1 or not list2:return list1 if list1 else list2# header = Nonep = Nonewhile list1 and list2:if list1.val <= list2.val:if header is None:header = list1p = list1else:p.next = list1p = list1list1 = list1.nextelse:if header is None:header = list2p = list2else:p.next = list2p = list2list2 = list2.nextif list1:p.next = list1elif list2:p.next = list2return header

java实现：
 

删除排序链表中的重复元素 1

给定一个已排序的链表的头 head ， 删除重复的后继元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：
在这里插入图片描述

输入：head = [1,1,2]
输出：[1,2]

示例 2：
在这里插入图片描述

输入：head = [1,1,2,3,3]
输出：[1,2,3]

python实现：递归算法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:return head# 至少两个节点cur = headif cur.val == cur.next.val:cur.next = cur.next.nextreturn self.deleteDuplicates(head)else:cur.next = self.deleteDuplicates(cur.next)return head

java实现：
在这里插入图片描述

 

删除排序链表中的重复元素 2

给一个已排序的链表的头 head ， 删除原始链表中所有 重复数字的节点 ，返回该链表 。

重点：已排序

示例 1：
在这里插入图片描述

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
 
示例 2：
在这里插入图片描述

输入：head = [1,1,1,2,3]
输出：[2,3]

python实现: 递归解决

  • 情况1：删除头节点重复的部分，继续递归处理剩下的部分；
  • 情况2：保留头节点，继续处理剩下的部分
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:return head# 至少两个节点cur = headif cur.val == cur.next.val: # 要删除头节点move = cur.next.nextwhile move and cur.val == move.val: # 移动到不相等的节点move = move.nextreturn self.deleteDuplicates(move)else:cur.next = self.deleteDuplicates(cur.next) # 保留头节点return head

同一段程序，多次提交，耗时和击败用户比率会不同；所以不用在乎这个击败比率。
在这里插入图片描述
java实现：
pending

 

环形链表1

给一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。存在环 ，则返回 true 。 否则，返回 false 。

以下pos不作为参数

示例 1：
在这里插入图片描述
输入：head = [3,2,0,-4], pos = 1
输出：true

示例 2：
在这里插入图片描述

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
在这里插入图片描述
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：你能用 O(1) 空间复杂度解决此问题吗？

python实现：

# 辅助空间 + 循环
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:temp = []cur = headwhile cur:temp.append(cur)if cur.next in temp:  # python内置方法也慢return Truecur = cur.nextreturn False# 双指针  一快 一慢   空间复杂度O(1)
# 快走两步  慢走一步  会在环内相遇
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:if head is None:return Falseslow_ptr = head  # 一次走一步fast_ptr = head  # 一次走两步while fast_ptr.next and fast_ptr.next.next:slow_ptr = slow_ptr.nextfast_ptr = fast_ptr.next.nextif fast_ptr is slow_ptr:return Truereturn False

java双指针
在这里插入图片描述

 

环形链表2

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
pos不传参，且不允许修改链表

示例 1：
在这里插入图片描述
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
 
示例 2：
在这里插入图片描述
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
 
示例 3：
在这里插入图片描述

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
 
python实现:

# 辅助空间 + 循环
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None:return Nonetemp = []cur = headwhile cur:temp.append(cur)if cur.next in temp:return cur.nextcur = cur.nextreturn None# 双指针  一快一慢   空间复杂度O(1)
# 快指针移动2步
# 漫指针移动1步
# 在环中相遇后，慢指针重置到head指针
# 然后两个指针均移动一步，直到再次相遇，即找到入环的节点
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None:return Noneslow_ptr = headfast_ptr = headhas_circle = Falsewhile fast_ptr.next and fast_ptr.next.next:slow_ptr = slow_ptr.nextfast_ptr = fast_ptr.next.nextif fast_ptr is slow_ptr:has_circle = Truebreakif has_circle:# 重置慢指针为headslow_ptr = head# 两个指针均移动一步，直到相遇while slow_ptr is not fast_ptr:slow_ptr = slow_ptr.nextfast_ptr = fast_ptr.next# 相遇则为入环节点return fast_ptrreturn None

优化前后时间对比：
在这里插入图片描述

java实现：
在这里插入图片描述

 

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
m,n 分别为链表A B的节点数。

图示两个链表在节点 c1 开始相交：
在这里插入图片描述

示例 1：
在这里插入图片描述

输入：listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
skipA = 2, skipB = 3 intersectVal = 8,
输出：node 8 对象

 
示例 2：
在这里插入图片描述
输入：listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 intersectVal = 2,
输出：node 2
 
示例 3：
在这里插入图片描述
输入：listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 intersectVal = 0,
输出：null

python 实现：
双指针 循环移动 直至相遇

# 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 headA is None or headB is None:return Nonepa = headApb = headBwhile pa is not pb:pa = pa.next if pa else headBpb = pb.next if pb else headAreturn pa

也可以计算链表的长度差值，较长的链表指针移动长度差个步子。
 
 

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
在这里插入图片描述

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

 
示例 2：
在这里插入图片描述

输入：head = [1,2]
输出：[2,1]
 
示例 3：

输入：head = []
输出：[]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
python实现：

在这里插入代码片

java实现：
在这里插入图片描述


http://www.ppmy.cn/news/1015447.html

相关文章

02_ansible配置文件中属性介绍

02_ansible配置文件中属性介绍

3.Ansible的配置文件 转自&#xff1a;https://ansible-tran.readthedocs.io/en/latest/docs/intro_configuration.html#accelerate-connect-timeout 3.1.Ansible的配置文件 Ansible的一些的设置可以通过配置文件完成.在大多数场景下默认的配置就能满足大多数用户的需求,在一…
阅读更多...
生态系统服务（InVEST模型）供给与需求、价值核算技术及人类活动、重大工程项目、自然保护区、碳中和等领域中实际案例分析

生态系统服务（InVEST模型）供给与需求、价值核算技术及人类活动、重大工程项目、自然保护区、碳中和等领域中实际案例分析

对接工作实际项目及论文写作&#xff0c;解决参会者关注的重点及实际项目过程问题&#xff0c;采取逐步延伸的逻辑&#xff0c;不论您是小白亦或是已经能够成功运行InVEST模型生成结果&#xff0c;您可以自由选择课程内容&#xff0c;如果您是小白老师手把手教您&#xff0c;如…
阅读更多...
算法通关村第六关——如何使用中序和后序来恢复一颗二叉树

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树

1 树的基础知识 1.1 树的定义 树(Tree)&#xff1a;表现得是一种层次关系&#xff0c;为 n &#xff08; n ≥ 0 &#xff09; n&#xff08;n≥0&#xff09; n&#xff08;n≥0&#xff09;个节点构成的有限集合&#xff0c;当n0时&#xff0c;称为空树&#xff0c;对于任一…
阅读更多...
h5端获取定位

h5端获取定位

第三方api有腾讯、高德、百度&#xff0c;下面简述腾讯位置api 引入jweixin.js <script> // 方法一 把js文件放到自己服务器上 import wx from /static/jweixin-1.6.0.js;// 方法二 vue在生命周期中应用 mounted() {const oScript document.createElement("scrip…
阅读更多...
Centos7配置网卡信息及固定IP

Centos7配置网卡信息及固定IP

找到网卡配置文件 Centos7之后的网卡配置文件统一放在/etc/sysconfig/network-scripts&#xff0c;在这个目录会找到以ifcfg开头的&#xff0c;和本机网卡数量对应的配置文件&#xff0c;如下: 执行该命令,进入该目录: cd /etc/sysconfig/network-scripts 再执行该命令 ll …
阅读更多...
vue手把手教学封装分页器

vue手把手教学封装分页器

1.vue中前台 <template><div><h6>"start":{{ pageStartEnd.start }},"当前页"&#xff1a;{{ pagenow }}"end":{{ pageStartEnd.end }}</h6><!-- 如果点击上一页按钮&#xff0c;当前页减去1&#xff0c;并且如果当…
阅读更多...
对 async/await 的理解

对 async/await 的理解

async/await 的理解 async/await 其实是 Generator 的语法糖&#xff0c;它能实现的效果都能用then 链来实现&#xff0c;它是为优化 then 链而开发出来的。从字面上来看&#xff0c;async 是“异步”的简写&#xff0c;await 则为等待&#xff0c;所以很好理解async用于申明一…
阅读更多...
固态硬盘 vs 机械硬盘：选择合适的存储方案

固态硬盘 vs 机械硬盘：选择合适的存储方案

随着计算机的快速发展&#xff0c;各种硬件组件如CPU、显卡以及制作工艺都取得了长足的进步&#xff0c;但是磁盘的发展相对较为缓慢&#xff0c;这也导致了磁盘性能在一定程度上限制了计算机的整体性能。为了解决这个问题&#xff0c;固态硬盘应运而生。 那么&#xff0c;我们…
阅读更多...
最新文章

Copyright @ 2022~2023