| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1454 |
第 321 场周赛 Q3 |
|
给你一个链表的头节点 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.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
nums = []
while head:
nums.append(head.val)
head = head.next
stk = []
for v in nums:
while stk and stk[-1] < v:
stk.pop()
stk.append(v)
dummy = ListNode()
head = dummy
for v in stk:
head.next = ListNode(v)
head = head.next
return dummy.next/**
* 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) {
List<Integer> nums = new ArrayList<>();
while (head != null) {
nums.add(head.val);
head = head.next;
}
Deque<Integer> stk = new ArrayDeque<>();
for (int v : nums) {
while (!stk.isEmpty() && stk.peekLast() < v) {
stk.pollLast();
}
stk.offerLast(v);
}
ListNode dummy = new ListNode();
head = dummy;
while (!stk.isEmpty()) {
head.next = new ListNode(stk.pollFirst());
head = head.next;
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
vector<int> nums;
while (head) {
nums.emplace_back(head->val);
head = head->next;
}
vector<int> stk;
for (int v : nums) {
while (!stk.empty() && stk.back() < v) {
stk.pop_back();
}
stk.push_back(v);
}
ListNode* dummy = new ListNode();
head = dummy;
for (int v : stk) {
head->next = new ListNode(v);
head = head->next;
}
return dummy->next;
}
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNodes(head *ListNode) *ListNode {
nums := []int{}
for head != nil {
nums = append(nums, head.Val)
head = head.Next
}
stk := []int{}
for _, v := range nums {
for len(stk) > 0 && stk[len(stk)-1] < v {
stk = stk[:len(stk)-1]
}
stk = append(stk, v)
}
dummy := &ListNode{}
head = dummy
for _, v := range stk {
head.Next = &ListNode{Val: v}
head = head.Next
}
return dummy.Next
}/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeNodes(head: ListNode | null): ListNode | null {
const nums = [];
for (; head; head = head.next) {
nums.push(head.val);
}
const stk: number[] = [];
for (const v of nums) {
while (stk.length && stk.at(-1)! < v) {
stk.pop();
}
stk.push(v);
}
const dummy = new ListNode();
head = dummy;
for (const v of stk) {
head.next = new ListNode(v);
head = head.next;
}
return dummy.next;
}# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(inf, head)
cur = head
stk = [dummy]
while cur:
while stk[-1].val < cur.val:
stk.pop()
stk[-1].next = cur
stk.append(cur)
cur = cur.next
return dummy.next/**
* 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) {
ListNode dummy = new ListNode(1 << 30, head);
Deque<ListNode> stk = new ArrayDeque<>();
stk.offerLast(dummy);
for (ListNode cur = head; cur != null; cur = cur.next) {
while (stk.peekLast().val < cur.val) {
stk.pollLast();
}
stk.peekLast().next = cur;
stk.offerLast(cur);
}
return dummy.next;
}
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
ListNode* dummy = new ListNode(1e9, head);
ListNode* cur = head;
vector<ListNode*> stk = {dummy};
for (ListNode* cur = head; cur; cur = cur->next) {
while (stk.back()->val < cur->val) {
stk.pop_back();
}
stk.back()->next = cur;
stk.push_back(cur);
}
return dummy->next;
}
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNodes(head *ListNode) *ListNode {
dummy := &ListNode{1 << 30, head}
stk := []*ListNode{dummy}
for cur := head; cur != nil; cur = cur.Next {
for stk[len(stk)-1].Val < cur.Val {
stk = stk[:len(stk)-1]
}
stk[len(stk)-1].Next = cur
stk = append(stk, cur)
}
return dummy.Next
}/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeNodes(head: ListNode | null): ListNode | null {
const dummy = new ListNode(Infinity, head);
const stk: ListNode[] = [dummy];
for (let cur = head; cur; cur = cur.next) {
while (stk.at(-1)!.val < cur.val) {
stk.pop();
}
stk.at(-1)!.next = cur;
stk.push(cur);
}
return dummy.next;
}