【力扣每日一题】力扣2478从链表中移除节点

题目来源

2478.从链表中移除节点

题目描述

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

解题思路

使用栈来解决这个问题

若栈为空，元素入栈；
若栈不为空，且栈顶元素不小于当前元素，元素入栈；
若栈不为空，且栈顶元素小于当前元素，进行出栈操作，直到栈空或者栈顶元素不小于当前元素，元素入栈。

代码

java代码使用双链表模拟栈

public class Solution {
    public ListNode removeNodes(ListNode head) {

        DoubleLink dhead = new DoubleLink();  // 栈底
        DoubleLink trail = dhead;             // 栈顶
        dhead.val = head;                     // 第一个元素入栈
        ListNode current = head.next;         // 当前元素
        while (current != null) {
            if (current.val > trail.val.val) { // 如果当前元素大于已经入栈的元素，出栈到栈顶元素大于当前元素
                while (trail != null && trail.val.val < current.val){
                    trail = trail.pre;
                }
            }
            if (trail == null) {                // 如果变为空栈，直接入栈
                dhead.val = current;
                dhead.pre = null;
                trail = dhead;
            }else {                             // 将元素入栈，并且连接指针
                trail.next = new DoubleLink();
                trail.next.pre = trail;
                trail = trail.next;
                trail.val = current;
                trail.pre.val.next = current;
            }
            current = current.next;
        }
        return dhead.val;
    }
}
// 题目指定的链表结构
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 DoubleLink{
    public DoubleLink pre;// 前驱
    public ListNode val; // 内容
    public DoubleLink next; // 后继
}

c++代码使用数组模拟栈

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode** nodeArray = new ListNode*[10000];
        nodeArray[0] = head;
        int index = 0;
        ListNode* current = head->next;
        while (current != nullptr) {
            if (current->val > nodeArray[index]->val) {
                while (index >= 0 && nodeArray[index]->val < current->val) {
                    index--;
                }
            }
            nodeArray[++index] = current;
            if (index > 0) {
                nodeArray[index - 1]->next = current;
            }
            current = current->next;
        }
        return nodeArray[0];
    }
};