2024.1.3力扣每日一题——从链表中移除节点

2024.1.3

- - 题目来源
  - 我的题解
  - - 方法一递归
    - 方法二栈
    - 方法三反转链表
    - 方法四单调栈+头插法

题目来源

力扣每日一题；题序：2487

我的题解

方法一递归

当前节点对其右侧节点是否删除无影响，因此可以对其右侧节点进行递归移除。

若当前节点为空，则返回空
若当前不为空，那么先对它的右侧节点进行移除操作，得到一个新的子链表，如果子链表的表头节点值大于该节点的值，那么移除该节点，否则将该节点作为子链表的表头节点，最后返回该子链表。
以 5,2,13,3,8 为例，递归过程如下图：

时间复杂度：O(n)
空间复杂度：O(1)

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;
    }else{
        return head;
    }
}

方法二栈

使用栈代替递归操作

时间复杂度：O(n)
空间复杂度：O(n)

 public ListNode removeNodes(ListNode head) {
        ListNode root=null;
        ListNode p=head;
        Deque<ListNode> stack=new LinkedList<>();
        while(p!=null){
            stack.push(p);
            p=p.next;
        }
        while(!stack.isEmpty()){
            if(root==null||stack.peek().val>=root.val){
                stack.peek().next=root;
                root=stack.peek();
            }
            stack.pop();
        }
        return root;
    }

方法三反转链表

直接先翻转整个链表，问题就变成保留大于等于左侧节点的节点

时间复杂度：O(n)
空间复杂度：O(1)

public ListNode removeNodes(ListNode head) {
       head=reverse(head);//先翻转整个链表
       ListNode p=head;
       while(p.next!=null){
           if(p.val>p.next.val){//当前节点大于右侧节点，右侧节点需要移除
               p.next=p.next.next;
           }else{
               p=p.next;
           }
       }
       return reverse(head);

    }
    //反转链表
    public ListNode reverse(ListNode head){
        ListNode root=new ListNode(-1);
        ListNode p=head;
        while(p!=null){
            ListNode nxt=p.next;
            p.next=root.next;
            root.next=p;
            p=nxt;
        }
        return root.next;
    }

方法四单调栈+头插法

先使用单调增栈存储最终需要留下的节点，然后使用头插的方式将这些节点连接起来

时间复杂度：O(n)
空间复杂度：O(n)

public ListNode removeNodes(ListNode head) {
        ListNode root=new ListNode(-1);
        Deque<ListNode> stack=new LinkedList<>();
        ListNode p=head;
        //使用单调增栈存储最终需要留下的节点
        while(p!=null){
            while(!stack.isEmpty()&&stack.peek().val<p.val){
                stack.pop();
            }
            stack.push(p);
            p=p.next;
        }
        //使用头插的方式将这些节点连接起来
        while(!stack.isEmpty()){
            ListNode cur=new ListNode(stack.pop().val);
            cur.next=root.next;
            root.next=cur;
        }
        return root.next;
    }