Medium

题目描述

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

解题思路

这道题要求移除所有右侧存在更大值的节点。我们可以从多个角度来思考：

方法一：递归（推荐） 核心思想是从右往左处理，先递归到链表末尾，然后在回溯过程中维护一个"右侧最大值"。当前节点如果小于右侧最大值就应该被移除，否则保留并更新最大值。

方法二：翻转链表 先翻转链表，然后从左到右遍历，维护一个递增的序列（单调递增栈的思想），最后再翻转回来。

方法三：单调栈 使用栈来模拟递归过程，先将所有节点入栈，然后出栈时构建结果链表，保持单调递增性。

递归方法最直观且代码简洁，时间复杂度O(n)，空间复杂度O(n)（递归栈空间）。翻转链表的方法空间复杂度为O(1)，但需要两次遍历。这里推荐使用递归方法。

代码实现

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        if (!head) return nullptr;
        
        head->next = removeNodes(head->next);
        
        if (head->next && head->val < head->next->val) {
            return head->next;
        }
        
        return head;
    }
};

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        head.next = self.removeNodes(head.next)
        
        if head.next and head.val < head.next.val:
            return head.next
        
        return head

public class Solution {
    public ListNode RemoveNodes(ListNode head) {
        if (head == null) return null;
        
        head.next = RemoveNodes(head.next);
        
        if (head.next != null && head.val < head.next.val) {
            return head.next;
        }
        
        return head;
    }
}

var removeNodes = function(head) {
    if (!head) return null;
    
    head.next = removeNodes(head.next);
    
    if (head.next && head.val < head.next.val) {
        return head.next;
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归方法翻转链表方法
时间复杂度O(n)O(n)
空间复杂度O(n)O(1)

其中 n 为链表节点数量。递归方法的空间复杂度主要来自递归调用栈。

相关题目