题解 | #删除链表峰值#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteNodes(struct ListNode* head ) {
    // write code here
    struct ListNode* pre = head,*cur = pre->next;
    while(cur->next)
    {
        if((cur->val > pre->val)&&(cur->val > cur->next->val))
        {
            pre->next = cur ->next;
        }
        else {
            pre = pre->next;
        }
        cur = cur->next;
    }
    return head;
}

1.考察的知识点：单链表

2.编程语言：C

3.解题思路 : 以1 3 2 4 5 为例子

分析题目可知左右边界峰值忽略不计，因此只需要考虑其他位置 3 2 4；

head指针指向链表头元素1；

定义pre、cur两个指针，分别表示当前指针的前一个位置、当前指针位置；

将pre指针指向当前head的位置，*pre = head；另一个指向pre的下一个位置；即在初始状态下pre指向1，cur指向3

然后分别向后顺序遍历，

当cur指针指到4时，此时cur->next 判断为true，

cur指针接着后移，到达右边界，此时cur->next不存在，得出循环边界为cur->next存在。

每次只需要考虑当前cur的值与pre、cur->next的值的大小，若cur的值比左边的pre和右边的cur->next更大，则执行pre->next = cur ->next，删除cur节点，更新cur节点；否则pre前移，更新cur节点。