面试高频TOP202

题目来源

牛客/题库/在线编程/算法篇/面试高频TOP202

链表

NB1 删除链表峰值

题目

描述

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

示例

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

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

代码

/**
 * 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
        if (head == nullptr || head->next==nullptr || head->next->next == nullptr) {
            return head;
        }
        ListNode *cur = head->next;
        ListNode *pre = head;
        ListNode *next = cur->next;
        while (next != nullptr) {
            if (cur->val>pre->val && cur->val>next->val) {
                pre->next = next;//改第一个节点的指向为第三个节点
                pre = next;//pre指针指向第三个节点，后移
                cur->next = nullptr;//断开中间节点
                cur = next->next;//cur后移2个位置
                if(cur == nullptr)
                break;//如果cur指向为空，说明next->next为空，说明数据已全部结束
                next = next->next->next;//后移2个位置
            }
            else{
                pre = cur;
                cur = next;
                next = next->next;
            }
        }
        return head;
    }
};

NB2 牛群排列去重

题目

描述

农场里有一群牛，每头牛都有一个独特的编号，编号由一个整数表示，整数范围是[0, 200]。牛群中的牛用单链表表示，链表已经按照非降序排列。
因为一些事故，导致一头牛可能多次出现在链表中。给你一个链表的头 head，删除链表中所有重复的编号，只留下所有牛的不重复编号。返回已排序的链表。

示例

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

代码

/**
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if (head==nullptr || head->next == nullptr) {//保证传进来的head链表至少有两个元素
            return head;
        }
        ListNode *next = head->next;
        ListNode *pre = head;
            while(next!=nullptr){//管else正常结束循环的
                if (next->val == pre->val) {
                    pre->next = next->next;//将前一个节点的指针指向第三个节点
                    next->next = nullptr;//断开重复节点
                    delete next;
                    pre = head;//
                    next = pre->next;//到第三个节点的下一个节点 段错误就说明next为空然后next->next了
                }else {//尽量不要用二级访问如cur->next->next 循环中容易段错误
                    pre = next;
                    next = next->next;
                }
            }
        return head;
    }
};