LeetCode 题解 2487. 从链表中移除节点

2487. 从链表中移除节点 - 力扣（Leetcode）

题解

思路一：递归逆序

struct ListNode* removeNodes(struct ListNode* head){
    if(head->next == NULL)//遍历到链表末尾
        return head;
    struct ListNode* after = removeNodes(head->next);
    if(after->val > head->val) return after;//如果after比head的数值更大，销毁head，返回after
    head->next = after;//否则此时为降序，将after链接在head之后
    return head;//返回after
}

思路二：暴力链表数组排序

struct Bucket_node {
    int num;
    int val;
    struct ListNode* address;
};
int cmp(const void* e1, const void* e2)
{
    struct Bucket_node a1 = *((struct Bucket_node*)e1), a2 = *((struct Bucket_node*)e2);
    if(a1.val != a2.val)
        return a2.val - a1.val;//先按数值降序排序
    else
        return a1.num - a2.num;//再按先后顺序升序排序
}

struct ListNode* removeNodes(struct ListNode* head){
    struct Bucket_node bucket[100000];//将链表转存为结构体数组，便于排序
    struct ListNode* ptr = head;
    int total = 0;
    while(ptr)//遍历链表所有节点
    {
        bucket[total].num = total;//保存顺序
        bucket[total].val = ptr->val;//保存数值
        bucket[total].address = ptr;//保存节点地址
        total++;
        ptr = ptr->next;
    }
    qsort(bucket, total, sizeof(struct Bucket_node), cmp);//按照val和num的结构体二级排序
    head = bucket[0].address;//将数值最大且位置最左的地址作为头节点
    ptr = bucket[0].address;
    int ptr_num = bucket[0].num;
    for(int i = 1; i < total; i++)
    {
        if(bucket[i].num > ptr_num)//如果在当前节点右侧
        {
            ptr->next = bucket[i].address;//链接下级节点
            ptr_num = bucket[i].num;//保存当前位置，用于比较左右顺序
            ptr = ptr->next;
        }
    }
    return head;
}