题目描述

题目链接:https://leetcode.cn/problems/remove-nodes-from-linked-list/description/

给你一个链表的头节点 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

方法1 递归

对于某个节点 我们可以对它的右节点进行递归
判断

• 如果当前节点为空 返回空
• 如果当前节点指向空 返回当前节点
• 判断当前节点是否小于 指向的节点，如果小于 移除当前节点，即返回下一个节点
• 否则返回当前节点

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {
    public ListNode removeNodes(ListNode head) {
    // 判空
        if(head == null || head.next == null){
            return head;
        }
        // 递归处理下一个节点
        head.next = removeNodes(head.next);
        // 如果当前节点小于下一个节点的值 移除当前节点
        if(head.val < head.next.val){
            return head.next;
        }
        return head;
    }
}

方法2 利用栈暂存节点

可以利用一个栈来存取节点，每次从栈中取出节点时 比较，如果大于当前节点 则 插入头部

class Solution {
    public ListNode removeNodes(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        // 先将 链表节点 入栈
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        // 入栈完 head = null
        // 开始出栈
        while(!stack.isEmpty()){
	        // 判断 栈当前的节点值 是不是大于等于 head 的值
	        // 如果满足条件 则 栈最上面的 节点 指向 head 同时 头节点往前移动
            if(head == null || stack.peek().val >= head.val){
                stack.peek().next = head;
                head = stack.peek();
            }
            stack.pop();
        }
        return head;
    }
}