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

发布时间:2024年01月05日

题目来源

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

解题思路

使用栈来解决这个问题

  1. 若栈为空,元素入栈;
  2. 若栈不为空,且栈顶元素不小于当前元素,元素入栈;
  3. 若栈不为空,且栈顶元素小于当前元素,进行出栈操作,直到栈空或者栈顶元素不小于当前元素,元素入栈。

代码

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];
    }
};

结果

java结果

c++结果

c++的大佬也太强了吧

文章来源:https://blog.csdn.net/qq_56460466/article/details/135374427
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。