题解 | #删除链表峰值#

题意分析：

农场主人有一群牛，每只牛都有一个编号，形成了一个链表。现在需要删除链表中比前后结点值都大的牛的编号（即删除那些在链表中比前后结点都大的节点）。需要注意的是，首尾的牛的编号不能删除。

时间复杂度：

分析代码中的时间复杂度。假设链表中有N个节点。

1. 在代码中，首先检查了链表是否为空或只有一个节点，这需要O(1)的时间。
2. 然后遍历链表，删除满足条件的节点。在最坏情况下，我们可能需要遍历整个链表一次，这需要O(N)的时间。
3. 因此，总的时间复杂度为O(N)。

代码分析：

代码中的解决思路是利用两个指针prev和curr分别表示当前节点和下一个节点，遍历链表，找到满足条件的节点并进行删除操作。具体的步骤如下：

1. 如果链表为空或者只有一个节点，直接返回头节点。
2. 初始化两个指针prev和curr，分别指向头节点和第二个节点。
3. 开始遍历链表： a. 如果prev节点的值小于curr节点的值，并且curr节点的值大于curr->next节点的值，则说明curr节点的值比前后节点都大，应该删除该节点。 b. 删除节点的操作是将prev->next指向curr->next，同时更新curr节点为curr->next，继续下一轮的遍历。 c. 如果curr节点的值不满足上述条件，说明该节点保留，将prev指针移动到curr，curr指针移动到curr->next，继续下一轮的遍历。
4. 最后返回头节点。

代码：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* deleteNodes(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* prev = head;
        ListNode* curr = head->next;
        while (curr->next) {
            if (prev->val < curr->val && curr->val > curr->next->val) {
                prev->next = curr->next;
                curr = curr->next;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }
        return head;
    }
};