LeetCode 题解：2487. 从链表中移除节点，递归

作者：Lee Chen

2025-02-06
福建
本文字数：1176 字
阅读完需：约 4 分钟

Problem: 2487. 从链表中移除节点

思路

这个问题要求我们移除链表中每个右侧有一个更大数值的节点。解决方案采用递归的方法，从链表的末尾开始向前处理，每次查看相邻两个节点的大小关系，将不符合要求的节点移除。

解题方法

递归基础：如果当前节点为空，直接返回它。这是递归的终止条件。
递归处理：对当前节点的下一个节点调用递归函数，以处理链表的剩余部分。
节点比较：比较当前节点和它的下一个节点的值。如果当前节点的值小于下一个节点的值，意味着当前节点应该被移除。
返回结果：根据比较结果，返回适当的节点作为新的链表头。

复杂度

时间复杂度: $O (n)$

空间复杂度: $O (n)$

Code

/** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var removeNodes = function(head) {  // 递归终止条件  if (!head) {    return head  }    // 递归处理链表的剩余部分  head.next = removeNodes(head.next)
  // 比较当前节点与下一个节点的值  if (head.next !== null && head.val < head.next.val) {    return head.next // 移除当前节点  } else {    return head // 保留当前节点  }};

复制代码

/** * 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) {        return head;      }
      // 递归处理链表的剩余部分      head.next = removeNodes(head.next);
      // 比较当前节点与下一个节点的值      if (head.next != null && head.val < head.next.val) {        return head.next; // 移除当前节点      } else {        return head; // 保留当前节点      }    }}

复制代码

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:      # 递归终止条件      if not head:        return head            # 递归处理链表的剩余部分      head.next = self.removeNodes(head.next)
      # 比较当前节点与下一个节点的值      if head.next and head.val < head.next.val:        return head.next # 移除当前节点      else:        return head # 保留当前节点

复制代码

发布于: 刚刚阅读数: 7

原文链接:【http://xie.infoq.cn/article/a7cddb23bf30c46505cda1504】。文章转载请联系作者。

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 题解：2487. 从链表中移除节点，递归

思路

解题方法

复杂度

Code

Lee Chen

评论