2487. 从链表中移除节点

2487. 从链表中移除节点

难度: 中等

来源: 每日一题 2024.01.03

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

/**
 * 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) {

    }
}

分析与题解

• 栈(先进后出)

  2024年第一篇博客, 开始喽~

  言归正传, 对于这个题目, 我们应该尝试使用栈的方式, 在遍历链表的过程中, 我们需要用栈的形式存储每一个链表节点, 并且为了方便后期的组装, 我们可以尝试双向队列来代替链表, 以便于后边后期从栈底取出元素.

  ArrayDeque<ListNode> deque = new ArrayDeque<ListNode>();
  

  那么什么时候触发删除操作呢? 如果当前节点的值比上一个节点的值大时, 也就是题意中的 每个右侧有一个更大数值的节点, 我们就从双向队列的栈顶依次取值, 直到不满足栈顶的值不大于当前节点的值.

  if (head.val > lastValue) {
      ListNode lastNode = deque.peekFirst();
      while (lastNode != null && lastNode.val < head.val) {
          deque.pollFirst();
          lastNode = deque.peekFirst();
      }
  }
  

  然后就是利用双向队列来重组链表了, 我们需要依次从栈底抛出节点然后组装链表.

  ListNode resultHeader = null, nowNode = null;
  while (!deque.isEmpty()) {
      ListNode node = deque.pollLast();
      if (resultHeader == null) {
          resultHeader = node;
          nowNode = node;
      } else {
          nowNode.next = node;
          nowNode = nowNode.next;
      }
  }
  

  接下来, 我们就看一下整体的题解过程.

  /**
  * 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) {
          // 用栈实现, 先入栈后出栈
          ArrayDeque<ListNode> deque = new ArrayDeque<ListNode>();
          int lastValue = 0;
          while (head != null) {
              if (head.val > lastValue) {
                  ListNode lastNode = deque.peekFirst();
                  while (lastNode != null && lastNode.val < head.val) {
                      deque.pollFirst();
                      lastNode = deque.peekFirst();
                  }
              }
              deque.addFirst(head);
              lastValue = head.val;
              head = head.next;
          }
          // 搞定之后重组链表
          ListNode resultHeader = null, nowNode = null;
          while (!deque.isEmpty()) {
              ListNode node = deque.pollLast();
              if (resultHeader == null) {
                  resultHeader = node;
                  nowNode = node;
              } else {
                  nowNode.next = node;
                  nowNode = nowNode.next;
              }
          }
          return resultHeader;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n * n²), 两层的循环遍历的时间复杂度
  • 空间复杂度: O(n), 双向队列所需要的空间复杂度与链表元素个数成线性关系

  结果如下所示.