首页 > 其他分享 >148.排序链表

148.排序链表

时间:2024-01-20 17:45:30浏览次数:35  
标签:prev ListNode nullptr 148 next 链表 curr 排序

1.题目介绍

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

2.题解

147.对链表进行插入排序中我们使用插入排序的方式对于链表进行排序
插入排序的时间复杂度是 O(n^2),其中 n 是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(nlog⁡n) 的时间复杂度和 O(1) 的空间复杂度,时间复杂度是 O(nlog⁡n) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n^2),其中最适合链表的排序算法是归并排序。

2.1 自底向上归并排序

思路

不同于使用递归自上而下的归并排序(从顶层开始逐层向下递归直到单个节点的情况),这里采用自底向上的归并排序方式
主要思路是:
1.遍历链表的得到总长度,从长度为1开始对链表进行拆分归并排序,得到长度为2,4,...Length的有序链表,作为外部大循环。
2.注意每次拆分时,都要隔绝链表和后续节点的联系(curr->next = nullptr)。归并后得到的链表都是相对独立的,这时候我们需要一个指针prev把它们再串成一个大链表,便于下次拆分。
3.总体拆分归并思路是得到两个独立的长度为subLength的有序链表,并获得它们的头结点,再通过调用归并排序函数将二者归并为一个大的有序链表。之后再使用指针prev,设置一个dummyHead虚拟头结点,串起所有子链表,再次进入。
4.由于一次拆分和归并可能并不能覆盖整个链表,即subLength<<1 < Length, 后续还要进行一次次的重复操作,也就是对于链表3,4;链表5,6....,这里还需要在一次的拆分归并操作中,记录下一次操作开始的头结点,这里可以用一个next来记录,并在最后将curr赋值为next,便于下一次循环开始。
5.这里拆分归并可能存在这几种情况:
5.1 最后一次拆分,剩余节点数小于subLength,这样得到head1后,curr遍历到链表1结尾,head2 = curr->next = nullptr; 然后curr = head2 = nullptr;
这里next部分是不走的,因为curr = nullptr; 之后合并head1和head2由于head2==nullptr,直接返回head1;最后prev将前面得到的链表和head1串起来,curr =
next = nullptr;结束本次循环。
5.2 最后一次拆分,剩余节点数小于等于subLength2,这样的到head1,head2后,curr遍历到链表2结尾,这里虽然curr不等于nullptr,走next判断的那一部分,但还是
next = curr->next = nullptr;会在本次结束循环;归并排序也是正常的归并两个链表,然后使用prev串起所有链表,结束。
5.3 最后依次拆分,剩余节点数大于subLength
2,这样的到head1,head2后,curr遍历到链表2结尾,next指向下一次while循环的链表1头结点,同时断掉链表2和后续节
点联系,后续步骤同理。
6.这里为何不直接使用prev = curr;让prev定位到链表末尾呢?这里注意!!!因为经过了归并排序后,链表顺序打乱,原来的curr现在不一定是链表的末尾!!!
while (prev->next != nullptr) { prev = prev->next; }

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr)
            return head;
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        /* 每次subLength*2,
         * 将链表从长度为1的小链表归并为长度为2,4,...,length的链表*/
        for (int subLength = 1; subLength < length;
             subLength <<= 1) { //这里<<=相当于+=
            /* prev用于新链表的建立, curr用于拆分链表*/
            ListNode *prev = dummyHead, *curr = dummyHead->next;
            /* 这里由于划分长度不同,一般一次拆分为两份链表归并并不够,需要进行重复多次操作*/
            while (curr != nullptr) {
                /* 1.找到两个独立有序的链表1和链表2 */
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next; //得到链表1尾部节点
                }
                ListNode* head2 = curr->next; //得到链表2头结点
                curr->next = nullptr; //断开链表1和后续节点连接
                curr = head2;         //更新curr位置为链表2头结点
                for (
                    int i = 1;
                    i < subLength && curr != nullptr && curr->next != nullptr;
                    i++) { //这里由于curr变化,while中的curr!=nullptr不能保证这里的curr,所以设置条件
                    curr = curr->next; //得到链表2尾部节点
                }
                ListNode* next = nullptr;
                /* 判断
                1.剩余节点数小于等于subLength,不够分出或刚好分出一个链表2,curr==nullptr,完成本次归并后结束
                2.
                剩余节点数大于sublength,可以分出一个完整链表2,接下来还有剩余,重复while循环*/
                if (curr != nullptr) {
                    next = curr->next;    //只要当前curr不为nullptr
                    curr->next = nullptr; //断掉链表2和后续节点的联系
                }
                /* 2.现在有了两个独立的链表1和链表2,我们就要进行排序归并 */
                ListNode* mergeNode = mergeList(head1, head2);
                prev->next =
                    mergeNode; //由于可能长度固定时,不止一次归并操作,需要用prev链接
                // prev = curr; //这是一种错误的想法,因为上面
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next; //为下次链表3和链表4的归并做准备(如果存在)
            }
        }
        return dummyHead->next;
    }

    ListNode* mergeList(ListNode* L1, ListNode* L2) {
        ListNode* prehead = new ListNode(-1);
        ListNode* prev = prehead;
        while (L1 != nullptr && L2 != nullptr) {
            if (L1->val <= L2->val) {
                prev->next = L1;
                prev = L1;
                L1 = L1->next;
            } else {
                prev->next = L2;
                prev = L2;
                L2 = L2->next;
            }
        }
        prev->next = L1 == nullptr ? L2 : L1;
        ListNode* ans = prehead->next;
        delete prehead;
        return ans;
    }
};

2.2

思路

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }
    
    ListNode* sortList(ListNode* head, ListNode* tail) {
        // 如果当前链表为空,直接返回
        if (head == nullptr) return head;
        
        // 如果当前范围只有一个节点,已经是有序的,直接返回
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }
        // 使用快慢指针找到中间节点
        ListNode* slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) fast = fast->next;
        }
        
        // 中间节点作为切分点,递归地对左右两部分进行排序,并合并
        ListNode* mid = slow;
        return mergeList(sortList(head, mid), sortList(mid, tail));
    }
    
    ListNode* mergeList(ListNode* L1, ListNode* L2) {
        ListNode* prehead = new ListNode(-1);
        ListNode* prev = prehead;
        while(L1 != nullptr && L2 != nullptr){
            if(L1->val <= L2->val){
                prev->next = L1;
                prev = L1;
                L1 = L1->next;
            }
            else{
                prev->next = L2;
                prev = L2;
                L2 = L2->next;
            }
        }
         prev->next = L1 == nullptr? L2:L1;  
         ListNode* ans = prehead->next;
         delete prehead;
         return ans;
    }
};

标签:prev,ListNode,nullptr,148,next,链表,curr,排序
From: https://www.cnblogs.com/trmbh12/p/17976828

相关文章

  • 可扩展、CY8C4148AZAS595、CY8C4148AZAS568、CY8C4148AZAS558支持更低的成本HMI应用,BT
    一、PSoC™Automotive4100SMaxMCU 1、说明PSoC4100SMax采用CAPSENSE技术,拥有7x7mm²、10x10mm²和14x14mm²三种封装尺寸,支持工业控制、汽车人机交互(HMI)、智能家居自动化及大型家用电器,如机器人、电感式传感器、洗衣机、冰箱、空调、智能温控器、打印机等。P......
  • linux内核链表
    linux内核的链表实现定义链表节点和初始化LIST_HEAD_INIT宏通过将next和prev都指向自身,来对节点进行初始化LIST_HEAD宏定义一个structlist_head类型的节点,并使用LIST_HEAD_INIT宏进行初始化点击查看代码structlist_head{ structlist_head*next,*prev;};#defineL......
  • Java - 排序
      冒泡排序升序排列importjava.util.Arrays;publicclassArrayDemo07{publicstaticvoidmain(String[]args){int[]a={1,4,5,3,14,12,51};int[]sort=sort(a);System.out.println(Arrays.toString(sort));}public......
  • 912.排序数组--堆排序
    1.题目介绍给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]2.题解2.1堆排序思路题目给了我们一个vector数组,要使用堆排序,我们首先要创建一个大根堆,再在这个大根堆的基础上对数......
  • 对象数组,根据字符串字段,并按默认方式排序
    sort在字符串的默认排序,是按unicode字节码排序的,一般字符串的排序可以通过strA.localeCompare(strB)来完成,但我这里必须要按字符串的默认方式排序。list=list.sort((a,b)=>{varjobA=a.Job;varjobB=b.Job;......
  • 数组的逆排序
    include<stdio.h>//实现函数初始化数组为全0voidInit(intarr[],intsz){inti=0;for(i=0;i<sz;i++){arr[i]=0;}}//打印数组的每个元素voidPrint(intarr[],intsz){inti=0;for(i=0;i<sz;i++){printf("%d",arr[i]);}printf(&qu......
  • 【算法】【线性表】【链表】LRU 缓存
    1 题目请你设计并实现一个满足  LRU(最近最少使用)缓存 约束的数据结构。实现 LRUCache 类:LRUCache(intcapacity) 以 正整数 作为容量 capacity 初始化LRU缓存intget(intkey) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。voidput......
  • 912.排序数组--归并排序
    1.题目介绍给你一个整数数组nums,请你将该数组升序排列。示例1:输入:nums=[5,2,3,1]输出:[1,2,3,5]示例2:输入:nums=[5,1,1,2,0,0]输出:[0,0,1,1,2,5]2.题解2.1归并排序思路归并排序利用了分治的思想来对序列进行排序。对一个长为n的待排序的序列,我们将其分解成两个......
  • 147.对链表进行插入排序
    1.题目介绍给定单个链表的头head,使用插入排序对链表进行排序,并返回排序后链表的头。插入排序算法的步骤:1.插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。2.每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的......
  • C# .net中PropertyDescriptor的使用和BindingList的ApplySort排序
    找了好多资料都是java中PropertyDescriptor的使用,至于C#中的都抄袭别人的,又讲不清楚怎么用。官方文档也没不会手把手教你怎么用,经过一下午的研究,结果如下1、找到PropertyDescriptor同一dll下的,使用TypeDescriptor反射出属性的PropertyDescriptorCollection,从这里拿出对应属性的P......