难度: Medium
给你一个链表的头节点 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运行时间: 312 ms
内存: 57.9 MB
# 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]:
# # 等价于求单调递减数列，但是链表的该如何去求呢，先写个作弊解法
# node = head
# arr = []
# while node is not None:
# while len(arr)> 0 and arr[-1]<node.val:
# arr.pop()
# arr.append(node.val)
# node = node.next
# head_new = ListNode(arr[0])
# node = head_new
# for i in range(1,len(arr)):
# node.next = ListNode(arr[i])
# node = node.next
# return head_new
# # 等价于求单调递减数列，对链表进行处理，也是相当于链表节点的替换,先保存全部节点，然后在按照顺序出栈
# st = []
# while head is not None:
# st.append(head)
# head = head.next
# while st:
# if head is None or st[-1].val >= head.val:
# st[-1].next = head
# head = st[-1]
# st.pop()
# return head
# 也可以用递归 sol 官方
if head is None:
return None
head.next = self.removeNodes(head.next)
if head.next is not None and head.val < head.next.val:
return head.next
else:
return head
题解采用的是递归方法来解决问题。首先，判断当前节点是否为尾节点，如果是，则直接返回该节点。否则递归调用当前函数处理当前节点的下一个节点。在递归返回后，比较当前节点的值与其下一个节点的值。如果当前节点的值小于下一个节点的值，则说明当前节点应该被移除，因此返回下一个节点。如果不是，则保留当前节点，返回当前节点。这样递归处理可以确保从链表末尾开始逐个检查节点，每次递归返回时都能决定是否保留当前节点。
时间复杂度: O(n)
空间复杂度: O(n)
# 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 is None:
return None
# 递归处理下一个节点
head.next = self.removeNodes(head.next)
# 比较当前节点与下一个节点的值，决定是否移除当前节点
if head.next is not None and head.val < head.next.val:
return head.next
else:
return head
在使用递归解决链表问题时，确保递归栈不溢出的主要方法是限制链表的长度或使用尾递归优化。然而，Python 并不默认支持尾递归优化，因此对于极长的链表，递归解决方案可能会导致栈溢出错误。为避免这种情况，可以考虑改用迭代方法处理链表，这种方法不依赖调用栈，因此更适合处理长链表。
递归解决方案中，每次递归调用都会增加堆栈的深度，导致大量资源消耗，尤其是当链表长度极大时，这会导致性能问题甚至栈溢出。为优化这一问题，可以转而使用迭代方法，该方法通过循环而非递归来遍历链表，从而有效控制资源消耗。此外，也可以考虑使用非递归的栈结构手动模拟递归过程，以减少系统调用栈的使用。
在Python中，当一个对象（如链表中的节点）不再被引用时，它将由Python的垃圾收集器自动回收。因此，当递归函数将一个节点的引用改为指向其他节点时，如果没有其他引用指向被移除的节点，该节点将自动成为垃圾收集的目标。不过，在一些没有自动垃圾收集的语言中，确实需要手动管理内存，如调用适当的函数来释放被移除节点的内存，以避免内存泄露。
题解中的算法自然支持所有节点值相等的情况。这是因为算法的核心逻辑是比较当前节点与下一个节点的值，只有当当前节点的值小于下一个节点的值时才移除当前节点。如果所有节点值相等，这一条件从不满足，因此所有节点都会被保留。这意味着算法无需特殊处理即可正确处理所有节点值相同的情况。