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.next
        n = len(nums)
        stack = []
        for i in range(n-1, -1, -1):
            if not stack: 
                stack.append(nums[i])
                continue
            if nums[i] >= stack[-1]: stack.append(nums[i])
        for i, num in enumerate(reversed(stack)):
            if i == 0:
                head = ListNode(num)
                p = head
            else:
                q = ListNode(num)
                p.next = q
                p = q
        return 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  # 删除 head
        head.next = node  # 不删除 head
        return head

简单的写法：

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        head.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, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def 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.next
            else: cur = cur.next
        return 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 = head
            A.append(head)
            head = head.next
        return A[0]

时间复杂度：O(n)
空间复杂度：O(1)