英文:
Remove nodes from linked list leetcode , time limit exceeded error
问题
给定一个链表的头节点。
删除每个节点，如果它右侧的任何节点都具有严格较大的值。
返回修改后链表的头节点。
我尝试使用递归方法，但仍然超出了时间限制，以下是我的代码：
class Solution {
public:
ListNode* solve(ListNode* head)
{
ListNode* temp;
if(head->next == NULL)
return head;
if(head->next->val > head->val)
{
head = head->next;
}
for(temp = head; temp->next != NULL; temp = temp->next)
{
while(temp->next->next != NULL)
{
if(temp->next->val < temp->next->next->val)
temp->next = temp->next->next;
}
}
solve(head);
return head;
}
ListNode* removeNodes(ListNode* head) {
return solve(head);
}
};
希望这对你有所帮助。
英文:
You are given the head of a linked list.
Remove every node which has a node with a strictly greater value anywhere to the right side of it.
Return the head of the modified linked list.
I have tried the method of recursion using the following code but nevertheless time limit exceeded is what I get
class Solution {
public:
ListNode* solve(ListNode* head)
{
ListNode* temp;
if(head->next=NULL)
return head;
if(head->next->val>head->val)
{
head=head->next;
}
for(temp=head;temp->next!=NULL;temp=temp->next)
{
while(temp->next->next!=NULL)
{
if(temp->next->val<temp->next->next->val)
temp->next=temp->next->next;
}
}
solve(head);
return head;
}
ListNode* removeNodes(ListNode* head) {
return solve(head);
}
};
答案1
得分: 1
Leetcode在这个问题上给出了一个上限，n = 10**5，所以如果你在n上有一个嵌套循环，那就是10_000_000_000次迭代。这在编写任何代码之前就明显会导致TLE（Time Limit Exceeded）。
在命令式语言中，递归通常不是处理链表问题的好工具：它更难访问前一个节点，容易引发栈溢出。链表的深度是线性的，而不像平衡树那样是对数深度。如果在这里使用递归，你需要一个栈大小为10**5。
这个问题要求我们删除任何节点，其中后面的节点有更大的值。为了实现这一点（从实际角度来看，这意味着在列表上进行一到三次遍历），我们可以重新制定问题以放宽其要求。
一个更简单的问题是删除任何节点，其值在其左边是严格更大的。现在，线性算法更加明显：遍历列表，跟踪到目前为止看到的最大值，并根据该信息确定节点的删除情况。
对于迭代中的每个节点：
- 如果其值小于目前为止看到的最大值，就删除它。
- 如果其值等于或大于目前为止看到的最大值，就保留它在列表中，并将其值设为新的最大值。
将这个策略应用到主问题上，我们可以反转列表，运行上述算法，然后再次反转列表并返回头节点。这是一个具有常数空间的三遍线性解决方案。
还有其他方法。通常情况下，你可以以时间换空间，以使用较少的遍历。
英文:
Leetcode gives a limit of n = 10**5 on this problem, so if you have a nested loop over n, that's 10_000_000_000 iterations. That's a clear TLE before any code is written.
Recursion is generally not a great tool for linked list problems in imperative languages: it's harder to access the previous node and it's easy to blow the stack. Linked lists have linear rather than logarithmic depth like balanced trees. If you use recursion here, you need a stack size of 10**5.
The problem is asking us to remove any node where there is another node with a greater value later in the list. To achieve this linearly (practically speaking, that means making one to three passes over the list), we could reformulate the problem to loosen its requirements.
A simpler problem is to remove any node with a value strictly greater to the left of it. Now, the linear algorithm is more apparent: walk the list, keeping track of the largest value seen so far, and determine removals for nodes based on that information.
For each node in the iteration:
- If its value is less than the greatest seen so far, remove it.
- If its value is equal to or greater than the greatest seen so far, keep it in the list and set its value as the new greatest.
Applying this strategy to the main problem, we could reverse the list, run the above algorithm, then reverse the list again and return the head. This is a three-pass linear solution with constant space.
Other approaches are possible. As is commonly the case, you can trade space for time to use fewer passes.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论