从leetcode链表中移除节点，超时错误

Question

你得到一个链表的头部。

删除在其右侧任何位置具有严格更大值的节点的每个节点。

返回修改后的链表的头部。

我已经尝试使用以下代码递归的方法，但我得到的是超过时间限制

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);
    
    }
};

Answer 1

Leetcode 在这个问题上给出了

n = 10**5

的限制，所以如果你有一个嵌套循环，那就是

10_000_000_000

迭代。在编写任何代码之前，这是一个清晰的 TLE。

递归通常不是命令式语言中链表问题的好工具：它更难访问前一个节点并且很容易炸毁堆栈。链表具有线性而不是像平衡树那样的对数深度。如果你在这里使用递归，你需要一个

10**5

.

的堆栈大小

问题是要求我们删除列表中后面有另一个具有更大值的节点的任何节点。为了线性地实现这一点（实际上，这意味着对列表进行一到三次传递），我们可以重新表述问题以放宽其要求。

一个更简单的问题是删除其左侧的值严格大于的任何节点。现在，线性算法更加明显：遍历列表，跟踪到目前为止看到的最大值，并根据该信息确定节点的移除。

对于迭代中的每个节点：

• 如果它的值小于迄今为止看到的最大值，则将其删除。
• 如果它的值等于或大于目前看到的最大值，将其保留在列表中并将其值设置为新的最大值。

将此策略应用于主要问题，我们可以反转列表，运行上述算法，然后再次反转列表并返回头部。这是具有恒定空间的三遍线性解决方案。

其他方法也是可能的。通常情况下，您可以用空间换取时间以使用更少的通行证。