算法练习--链表相关

文章目录

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

合并两个有序链表

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

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

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

示例 2：
输入： ${l1}$ = [], ${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