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

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;}

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