当前位置：首页 > article >正文

快手手撕力扣2487 从链表中移除节点单调栈递归

article 2024/11/14 1:28:22

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

👨‍🏫 参考题解

💖 递归解法

在这里插入图片描述

/**
 * 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.next == 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.
 * 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)
	{
		LinkedList<ListNode> stack = new LinkedList<>();
		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;
	}
}