如何做免费的网站,微信小程序上线流程,自建网站平台,php网站开发几技术难点LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】 题目描述#xff1a;解题思路一#xff1a;可以将链表转为数组#xff0c;然后从后往前遍历#xff0c;遇到大于等于当前元素的就入栈#xff0c;最终栈里面的元素即是最终的答案。解题思路二#xff1a;递归解题思路一可以将链表转为数组然后从后往前遍历遇到大于等于当前元素的就入栈最终栈里面的元素即是最终的答案。解题思路二递归思路是递归到最后head后面是node如果node的值大于head的值那么删除head。否则不删除。解题思路三迭代两次反转链表解题思路四单调栈不解释 题目描述
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。
示例 1
输入head [5,2,13,3,8] 输出[13,8] 解释需要移除的节点是 5 2 和 3 。
节点 13 在节点 5 右侧。节点 13 在节点 2 右侧。节点 8 在节点 3 右侧。
示例 2 输入head [1,1,1,1] 输出[1,1,1,1] 解释每个节点的值都是 1 所以没有需要移除的节点。
提示
给定列表中的节点数目在范围 [1, 105] 内 1 Node.val 105
解题思路一可以将链表转为数组然后从后往前遍历遇到大于等于当前元素的就入栈最终栈里面的元素即是最终的答案。
不过这种思路也许有些投机取巧没有用到纯粹的链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:nums []while head:nums.append(head.val)head head.nextn len(nums)stack []for i in range(n-1, -1, -1):if not stack: stack.append(nums[i])continueif nums[i] stack[-1]: stack.append(nums[i])for i, num in enumerate(reversed(stack)):if i 0:head ListNode(num)p headelse:q ListNode(num)p.next qp qreturn head
时间复杂度O(n) 只是遍历了两遍链表 空间复杂度O(n) 存储的数组
解题思路二递归思路是递归到最后head后面是node如果node的值大于head的值那么删除head。否则不删除。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:if head.next is None: return head # 输入保证链表不为空node self.removeNodes(head.next) # 返回的链表头一定是最大的if node.val head.val: return node # 删除 headhead.next node # 不删除 headreturn head简单的写法
class Solution:def removeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:if not head: return headhead.next self.removeNodes(head.next)return head.next if head.next and head.val head.next.val else head 时间复杂度O(n)其中 n 为链表的长度。 空间复杂度O(n) 栈空间
解题思路三迭代两次反转链表
翻转链表看LeetCode-206. 反转链表【双指针递归】这里用的是简单的双指针来翻转链表然后遇到比当前元素小的就可以直接删除然后再次翻转链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre, cur None, headwhile cur:nxt cur.nextcur.next prepre curcur nxtreturn predef removeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:cur head self.reverseList(head)while cur.next:if cur.val cur.next.val: cur.next cur.next.nextelse: cur cur.nextreturn self.reverseList(head)时间复杂度O(n) 只是遍历了两遍链表 空间复杂度O(1) 原地翻转
解题思路四单调栈不解释
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNodes(self, head: Optional[ListNode]) - Optional[ListNode]:A []while head:while A and A[-1].val head.val: A.pop()if A: A[-1].next headA.append(head)head head.nextreturn A[0]时间复杂度O(n) 空间复杂度O(1)
