【LeetCode每日一题】2487. 从链表中移除节点(调用栈+递归+翻转链表)

发布时间:2024年01月03日

2024-1-3

2487. 从链表中移除节点

在这里插入图片描述

方法一:调用栈

1.将所有节点按顺序压入栈中

2.从栈顶依次查看元素

3.当栈顶节点的值大于新链表表头的值,将该节点插入新链表的表头

4.否则移除该节点

    public ListNode removeNodes(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while (head!=null){
            stack.push(head);
            head = head.next;
        }
        while (!stack.isEmpty()){
            if (head==null||stack.peek().val>=head.val){
                stack.peek().next = head;
                将该节点插入新链表的表头
                head = stack.peek();
                //表头前移
                
            }
            stack.pop();
        }
        return head;

    }
方法二:递归

1.节点为空返回

2.不为空,对右侧节点进行判断

3.比右侧节点小,移除当前结点,返回下一个结点

4.比右侧节点大,返回当前结点

    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;
        }
        
    }
方法三:翻转链表

1.翻转链表、要求改为:移除每一个左侧有一个更大数值的节点。

2.不断移除右结点,除非右结点的值大于等于当前结点

3.再翻转回来

    public ListNode removeNodes3(ListNode head) {
        head = reverse(head);
        ListNode cur = head;
        while (cur.next!=null){
            if (cur.val>cur.next.val){
                //当前值比右边值大,删除右边结点
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return reverse(head);
        //翻转回来

    }

    public ListNode reverse (ListNode head){
        //翻转链表
        ListNode dummy = new ListNode();
        while (head!=null){
            ListNode cur = head;
            head = head.next;
            cur.next = dummy.next;
            dummy.next = cur;
        }
        return dummy.next;
    }

点击移步博客主页,欢迎光临~

偷cyk的图

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