删除链表峰值

• 链表基础操作

题目描述

农场主人有一群牛，他给每只牛都打了一个编号，编号由整数表示。这些牛按照编号的大小形成了一个链表。现在农场主人想删除链表中比前后结点值都大的牛的编号，你能帮他设计一个算法来实现这个功能吗？注意，只考虑删除前，首尾的牛的编号不删除。

示例：

输入：{1,3,2,4,5}
返回值：{1,2,4,5}

C++实现

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteNodes(ListNode* head) {
        // write code here
        // prev -> curr -> next
        // prev->next = next
        ListNode *curr = head;
        while (curr && curr->next && curr->next->next) {
            if (curr->val < curr->next->val && curr->next->val > curr->next->next->val) {
                ListNode *tmp = curr->next;
                curr->next = curr->next->next;
                delete tmp;
            }
            curr = curr->next;
        }
        
        return head;
    }
};

golang实现

package main
//import "fmt"
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func deleteNodes( head *ListNode ) *ListNode {
    // write code here
    curr := head
    for curr != nil && curr.Next != nil && curr.Next.Next != nil {
        if curr.Val < curr.Next.Val && curr.Next.Val > curr.Next.Next.Val {
            curr.Next = curr.Next.Next
        }
        curr = curr.Next
    }

    return head
}