题目
给你一个链表的头节点
head。移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点
head。
解题思路
- 移除每个右侧有一个更大数值的节点，所以可以利用深度遍历，从后往前进行比较；
- 创建变量max来表示当前右侧的最大值；
- 将最后节点的值赋值给max；
- 若当前节点的值小于当前节点则移除，否则修改max为当前节点的值，链表是单向的，直接移除当前节点不好移除，可以将下个节点的值和next赋值给当前节点，即用下个节点取代当前节点。
代码展示
class Solution { private int max = 0; public ListNode removeNodes(ListNode head) { dfs(head); return head; } private void dfs(ListNode root){ if(root == null){ return; } dfs(root.next); if(root.val < max){ root.val = root.next.val; root.next = root.next.next; } else { max = root.val; } } }
