给你一个链表的头节点 head
。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head
。
示例 1:
输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
示例 2:
输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。
提示:
[1, 105]
内1 <= Node.val <= 105
递归
通过递归来遍历链表,同时比较当前节点和下一个节点的值,如果下一个节点的值大于当前节点的值,就将当前节点移除,返回下一个节点,否则保留当前节点,返回当前节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptrptr) {}
* ListNode(int x) : val(x), next(nullptrptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
if(head == nullptr){
return nullptr;
}
head->next = removeNodes(head->next);
if(head->next != nullptr && head->next->val > head->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) {
if(head == null){
return null;
}
head.next = removeNodes(head.next);
if(head.next != null && head.next.val > head . val){
return head.next;
}else{
return head;
}
}
}