温州网站排名优化公司,室内设计效果图手绘线稿,重庆网站建设制作,汽车网站开发与实现 论文2024.1.3 题目来源我的题解方法一 递归方法二 栈方法三 反转链表方法四 单调栈头插法 题目来源
力扣每日一题#xff1b;题序#xff1a;2487
我的题解
方法一 递归 当前节点对其右侧节点是否删除无影响#xff0c;因此可以对其右侧节点进行递归移除。 若当前节点为空头插法 题目来源
力扣每日一题题序2487
我的题解
方法一 递归 当前节点对其右侧节点是否删除无影响因此可以对其右侧节点进行递归移除。 若当前节点为空则返回空若当前不为空那么先对它的右侧节点进行移除操作得到一个新的子链表如果子链表的表头节点值大于该节点的值那么移除该节点否则将该节点作为子链表的表头节点最后返回该子链表。 以 5,2,13,3,8 为例递归过程如下图 时间复杂度O(n) 空间复杂度O(1) public ListNode removeNodes(ListNode head) {if(headnull){return null;}head.nextremoveNodes(head.next);// 如果当前比后面的小这需要删除if(head.next!nullhead.valhead.next.val){return head.next;}else{return head;}
}方法二 栈 使用栈代替递归操作 时间复杂度O(n) 空间复杂度O(n) public ListNode removeNodes(ListNode head) {ListNode rootnull;ListNode phead;DequeListNode stacknew LinkedList();while(p!null){stack.push(p);pp.next;}while(!stack.isEmpty()){if(rootnull||stack.peek().valroot.val){stack.peek().nextroot;rootstack.peek();}stack.pop();}return root;}方法三 反转链表 直接先翻转整个链表问题就变成保留大于等于左侧节点的节点 时间复杂度O(n) 空间复杂度O(1) public ListNode removeNodes(ListNode head) {headreverse(head);//先翻转整个链表ListNode phead;while(p.next!null){if(p.valp.next.val){//当前节点大于右侧节点右侧节点需要移除p.nextp.next.next;}else{pp.next;}}return reverse(head);}//反转链表public ListNode reverse(ListNode head){ListNode rootnew ListNode(-1);ListNode phead;while(p!null){ListNode nxtp.next;p.nextroot.next;root.nextp;pnxt;}return root.next;}方法四 单调栈头插法 先使用单调增栈存储最终需要留下的节点然后使用头插的方式将这些节点连接起来 时间复杂度O(n) 空间复杂度O(n) public ListNode removeNodes(ListNode head) {ListNode rootnew ListNode(-1);DequeListNode stacknew LinkedList();ListNode phead;//使用单调增栈存储最终需要留下的节点while(p!null){while(!stack.isEmpty()stack.peek().valp.val){stack.pop();}stack.push(p);pp.next;}//使用头插的方式将这些节点连接起来while(!stack.isEmpty()){ListNode curnew ListNode(stack.pop().val);cur.nextroot.next;root.nextcur;}return root.next;}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
