LeetCode-2487. 从链表中移除节点【栈 递归 链表 单调栈】

题目描述：

给你一个链表的头节点 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, 10⁵] 内
1 <= Node.val <= 10⁵

解题思路一：可以将链表转为数组，然后从后往前遍历，遇到大于等于当前元素的就入栈，最终栈里面的元素即是最终的答案。

不过这种思路也许有些投机取巧，没有用到纯粹的链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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)