首页 > 编程语言 >[LeetCode] 2487. Remove Nodes From Linked List

[LeetCode] 2487. Remove Nodes From Linked List

时间:2024-05-07 13:00:26浏览次数:27  
标签:node head ListNode cur val 2487 List Remove next

You are given the head of a linked list.

Remove every node which has a node with a greater value anywhere to the right side of it.

Return the head of the modified linked list.

Example 1:
Example 1
Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.

  • Node 13 is to the right of node 5.
  • Node 13 is to the right of node 2.
  • Node 8 is to the right of node 3.

Example 2:
Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

Constraints:
The number of the nodes in the given list is in the range [1, 105].
1 <= Node.val <= 105

从链表中移除节点。

给你一个链表的头节点 head 。 移除每个右侧有一个更大数值的节点。 返回修改后链表的头节点 head 。

思路

根据题意,如果某个 node 的右侧有一个比他 val 更大的 node,需要把这个 node 删除。那么这里我们可以反过来思考,如果我们从右往左遍历整个链表,我们可以先把第一个节点的 val 当做最大值,记为 max,再往左遍历的时候,如果当前节点值比 max 小,则把当前节点移除;否则把当前节点的节点值记为 max,继续往左遍历。这样做的好处是,我们只需要遍历一次链表,就可以把所有需要删除的节点都删除掉。不过我们需要将 input 链表整个反转一次,遍历一次,再反转回去。

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * 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) {
        // corner case
        if (head == null || head.next == null) {
            return head;
        }

        // normal case
        head = reverse(head);
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        int max = 0;
        while (cur.next != null) {
            if (cur.next.val < max) {
                cur.next = cur.next.next;
            } else {
                max = cur.next.val;
                cur = cur.next;
            }
        }
        head = reverse(head);
        return head;
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

标签:node,head,ListNode,cur,val,2487,List,Remove,next
From: https://www.cnblogs.com/cnoodle/p/18177028

相关文章

  • [992] Remove holes within polygons in a shapefile
    Toremoveholeswithinpolygonsinashapefile,youcanusethegeopandaslibraryinPython.Here'showyoucandoit:importgeopandasasgpd#Readtheshapefilegdf=gpd.read_file('path_to_shapefile.shp')#Removeholeswithinpolygon......
  • 开源电子邮件营销平台 listmonk 使用教程
    做产品肯定要做电子邮件营销,特别是面向海外的产品,电子邮件营销已成为企业与客户沟通、建立品牌忠诚度和推动销售的重要工具,可以直接接触到目标受众,提供个性化内容,并以相对较低的成本获得可观的投资回报。你看,MEAP又来提醒我买电子书了!做电子邮件营销首先需要考虑的是选哪个电子......
  • Phone List
    题目描述输入格式输出格式样例样例输入2391197625999911254265113123401234401234598346样例输出NOYES数据范围与提示这道题的三条判断是否存在前缀的标准:当在建树字符串已经到结尾时,如果该点有结束标记,那肯定是前缀(不是真前缀)当在建树字符串已经到......
  • grid 与 treelist 的区别
    TreeList与Grid的主要区别体现在数据结构、展示方式和应用场景上。以下是具体的分析:数据结构:TreeList:TreeList是一种树状的数据结构,它可以理解为是一个有序、可重复的树状列表。这种数据结构不仅实现了List接口,还融入了树的特性,如父子节点的关系,这使得它在处理具有层级关系的......
  • devexpress中 cxTreeList 与 cxVirtualTreeList 区别
    在DevExpress控件库中,cxTreeList和cxVirtualTreeList都是用于展示层级数据的控件,但它们在使用场景、性能优化和数据加载方式等方面有所不同。以下是两者之间的主要区别:数据展示与交互:cxTreeList:提供了一个传统的树形列表视图,用户可以直观地看到数据的层级结构,并通过展开和折......
  • List的remove()方法详解
    https://blog.csdn.net/anxin_hw/article/details/128312846一、错误使用场景1、普通for循环遍历List删除指定元素,list.remove(index)示例:将姓张的名字移除掉List<String>nameList=newArrayList<>(Arrays.asList("张三","李四","王五","赵六"));na......
  • CMakeLists.txt --- install使用
    例:cmake_minimum_required(VERSION3.9)project(test)set(CMAKE_BUILD_TYPEDebug)add_library(hahatest.cpp)install(TARGEThahaDESTINATION/home/linxisuo/project/test)install(DIRECTORY${CMAKE_SOURCE_DIR}/testDESTINATION/home/linxisuo)说明:1.安装......
  • CMakeListx.txt --- include_directories和target_include_directories命令
    1. include_directories语法include_directories([AFTER|BEFORE][SYSTEM]dir1[dir2...])作用将指定目录添加到编译器的头文件搜索路径之下,指定的目录被解释成当前源码路径的相对路径。参数默认情况下,include_directories命令会将目录添加到列表最后,可以通过命令设置......
  • CMakeLists.txt --- 导入接口库(预编译库)
    以接口库的方式导入预编译库cmake_minimum_required(VERSION3.9)project(test)set(CMAKE_BUILD_TYPEDebug)set(CMAKE_C_FLAGS"$ENV{CFLAGS}-O2-Wall-pthread")set(CMAKE_CXX_FLAGS"$ENV{CFLAGS}-O2-Wall-pthread-std=c++11-std=gnu++11")#设置mo......
  • python教程3.1:数据类型:字符串+列表list
    一、字符串字符串是⼀个有序的字符的集合,⽤于在计算机⾥存储和表示⽂本信息 常用操作二、列表list[]内以逗号分隔,按照索引,存放各种数据类型,每个位置代表⼀个元素特征 1、增加操作   追加,数据会追加到尾部 2、删除操作3、修改操作 4、查找操作 如果......