精华内容
下载资源
问答
  • 链表排序
    千次阅读
    2022-04-28 23:03:05

    1 题目

    题目:链表排序(Sort List)
    描述:在 O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序。

    lintcode题号——98,难度——medium

    样例1:

    输入:list = 1->3->2->null
    输出:1->2->3->null
    解释:给链表排序.
    

    样例2:

    输入:list = 1->7->2->6->null
    输出:1->2->6->7->null
    解释:给链表排序.
    

    2 解决方案

    2.1 思路

      题目要求排序,在O(nlogn)时间复杂度内,空间复杂度要求常数级,满足时间复杂度的排序可以想到快速排序和归并排序,满足空间复杂度的只有快速排序,但题目排序的对象是链表,归并排序在数组上的空间复杂度是O(n),但对链表排序时不需要额外的数据结构来存储临时数据,所以在链表上的归并排序的空间复杂度只有O(1),本题使用快排和归并都可以。

    2.2 时间复杂度

      时间复杂度为O(n * log n)。

    2.4 空间复杂度

      空间复杂度为O(1)。

    3 源码

    细节:

    1. 使用快、慢指针的方式来找链表的中点。
    2. fast指针起点位置向后移动一位,符合整数计算偏左的特点,且不用特殊处理链表长度为2的情况。
    3. 递归时先处理后半段,再将中点赋空,断开后半段,再处理前半段。

    C++版本:

    /**
    * Definition of singly-linked-list:
    * class ListNode {
    * public:
    *     int val;
    *     ListNode *next;
    *     ListNode(int val) {
    *        this->val = val;
    *        this->next = NULL;
    *     }
    * }
    */
    /**
    * @param head: The head of linked list.
    * @return: You should return the head of the sorted linked list, using constant space complexity.
    */
    ListNode* sortList(ListNode *head) {
        // write your code here
        if (head == nullptr || head->next == nullptr) // 跳过链表长度为0和1的情况
        {
            return head;
        }
    
        // 找到链表中点
        ListNode * mid = head;
        ListNode * fast = head->next; // fast指针起点位置向后移动一位,符合整数计算偏左的特点,且不用特殊处理链表长度为2的情况
        while (fast != nullptr && fast->next != nullptr)
        {
            mid = mid->next;
            fast = fast->next->next;
        }
    
        ListNode * right = sortList(mid->next); // 先排后半段
        mid->next = nullptr; // 断开后半段
        ListNode * left = sortList(head); // 再排前半段
    
        return mergeTwoSortedList(left, right);
    }
    
    ListNode * mergeTwoSortedList(ListNode * left, ListNode * right)
    {
        if (left == nullptr)
        {
            return right;
        }
        if (right == nullptr)
        {
            return left;
        }
    
        ListNode dummyNode(0);
        ListNode * cur = &dummyNode;
        while (left != nullptr && right != nullptr)
        {
            if (left->val < right->val)
            {
                cur->next = left;
                left = left->next;
                cur = cur->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
                cur = cur->next;
            }
        }
    
        if (left != nullptr)
        {
            cur->next = left;
        }
        if (right != nullptr)
        {
            cur->next = right;
        }
    
        return dummyNode.next;
    }
    
    更多相关内容
  • 链表排序

    千次阅读 2020-12-09 10:39:30
    下面的排序只针对无头结点的单链表,当然有头节点稍微改改就可以了 选择排序 选择排序就是每次选一个最小的,放到前面 为了方便操作,创造一个头结点 /** * Definition of singly-linked-list: * class ...

    下面的排序只针对无头结点的单链表,当然有头节点稍微改改就可以了

    选择排序

    选择排序就是每次选一个最小的,放到前面

    为了方便操作,创造一个头结点

    /**
     * Definition of singly-linked-list:
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *        this->val = val;
     *        this->next = NULL;
     *     }
     * }
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            //空链表或者只有一个节点
            if(head==nullptr||head->next==nullptr)return head;
            ListNode* temp=new ListNode(0);
            temp->next=head;
            for(ListNode* r=temp;r->next->next!=nullptr;r=r->next){
                ListNode* p,*q;
                //p用来存储最小的节点的前驱
                for(p=r,q=r->next;q->next!=nullptr;q=q->next){
                    if(q->next->val<p->next->val){
                        p=q;
                    }
                }
                q=p->next;//指向最小
                p->next=q->next;//断链
                
                //拼接
                q->next=r->next;
                r->next=q;
            }
            head=temp->next;
            delete temp;
            return head;
        }
    };

    插入排序

    也创建一个头结点方便操作

    插入排序由于链表不能往前迭代,所以只能在有序的部分遍历,找插入位置

    所以这个不是真正意义上的插入排序

    /**
     * Definition of singly-linked-list:
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *        this->val = val;
     *        this->next = NULL;
     *     }
     * }
     */
    
    class Solution {
    public:
        /**
         * @param head: The first node of linked list.
         * @return: The head of linked list.
         */
        ListNode * insertionSortList(ListNode * head) {
            // write your code here
            //空链表或者只有一个节点
            if(head==nullptr||head->next==nullptr)return head;
            ListNode* temp=new ListNode(1);
            temp->next=head;
            //temp的链表现在是有序的那部分
            ListNode* p=head->next,*q,*r;
            head->next=nullptr;
            while(p){
                q=temp;
                //找插入位置
                while(q->next&&q->next->val<=p->val){
                    q=q->next;
                }
                r=p->next;
                p->next=q->next;
                q->next=p;
                p=r;
            }
            return temp->next;
        }
    };

    快速排序

    由于不能往前迭代,所以只能换种方法

    p指向小于哨兵的最后一个,q是用来迭代的,如果q当前的值小于哨兵,就把他和p后面的交换,大概感觉就是下面这张图

     

    /**
     * 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:
        void helper(ListNode* head,ListNode* tail){
            if(head==tail||head->next==tail)return;
            int val=head->val;
            ListNode* p=head;
            for(ListNode* q=head->next;q!=tail;q=q->next){
                if(q->val<val){
                    p=p->next;
                    if(p!=q){
                        swap(p->val,q->val);
                    }
                }
            }
            swap(head->val,p->val);
            helper(head,p);
            helper(p->next,tail);
        }
        ListNode* sortList(ListNode* head) {
            if(head==nullptr||head->next==nullptr)return head;
            helper(head,nullptr);
            return head;
        }
    };

    归并排序

    在链表排序中,归并应该算最快的

    用快慢指针找中间,然后左边归并,右边归并,然后合并,都是基本操作

    唯一要注意的是如果是空链表或者是只有一个节点,要直接返回,不然会死循环

    /**
     * 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* merge(ListNode* p,ListNode* q){
            if(q==nullptr)return p;
            else if(p==nullptr)return q;
            ListNode* r,*tail=nullptr;
            while(p!=nullptr&&q!=nullptr){
                if(p->val<=q->val){
                    if(tail!=nullptr){
                        tail->next=p;
                        tail=p;
                    }
                    else{
                        r=tail=p;
                    }
                    p=p->next;
                }
                else{
                    if(tail!=nullptr){
                        tail->next=q;
                        tail=q;
                    }
                    else{
                        r=tail=q;
                    }
                    q=q->next;
                }
            }
            if(p==nullptr)p=q;
            tail->next=p;
            return r;
        }
        ListNode* sortList(ListNode* head) {
            if(head==nullptr||head->next==nullptr)return head;
            ListNode* slow=head,*fast=head;
            while(fast->next!=nullptr&&fast->next->next!=nullptr){
                slow=slow->next;
                fast=fast->next->next;
            }
            fast=slow->next;
            slow->next=nullptr;
            head=sortList(head);
            fast=sortList(fast);
            return merge(head,fast);
        }
    };

    总结

    效率上,归并应该是最快的

    在leetcode上,只有归并能过

    https://leetcode.com/problems/sort-list/submissions/

    下面这个是lintcode链表插入排序,用插入和选择都能过

    https://www.lintcode.com/problem/insertion-sort-list/

    下面这个是lintcode链表排序,快排和归并能过,目测选择和插入过不了

    https://www.lintcode.com/problem/sort-list/description

    下面这个是牛客网,虽然说是选择排序,但是只有归并能过

    https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=188&&tqId=36717&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

     

    C++完整版

    #include<iostream>
    #include<random>
    #include<vector>
    #include<algorithm>
    using namespace std;
    /**
     * 链表节点
     */
    template<typename T>
    class Node{
    public:
        T data;
        Node<T>* next;
        Node():next(nullptr){}
        explicit Node(const T& data):data(data),next(nullptr){}
    };
    /**
     * 无头结点单链表
     */
    template<typename T>
    class LinkedList{
    private:
        Node<T>* head;//链表
        /**
         * 两个链表归并
         * @param p 链表1
         * @param q 链表2
         * @return 归并后的链表
         */
        static Node<T>* merge(Node<T>* p,Node<T>* q){
            if(nullptr == p){
                return q;
            }
            else if(nullptr == q){
                return p;
            }
            Node<T>* r;//合并后的链表
            Node<T>* tail= nullptr;//合并后的链表的最后一个节点
            while(p!=nullptr&&q!=nullptr){
                if(p->data<=q->data){
                    if (tail != nullptr) {
                        tail->next = p;
                        tail = p;
                    }
                    else {
                        r = tail = p;
                    }
                    p=p->next;
                }
                else{
                    if (tail != nullptr) {
                        tail->next = q;
                        tail = q;
                    }
                    else {
                        r = tail = q;
                    }
                    q=q->next;
                }
            }
            if(p==nullptr){
                p=q;
            }
            tail->next=p;
            return r;
        }
        /**
         * 归并排序
         * @param head 链表
         * @return 排序后的链表
         */
        static Node<T>* mergeSort(Node<T>* head){
            //空链表或者只有一个元素
            if(head==nullptr||head->next==nullptr){
                return head;
            }
            //快慢指针,找中间节点
            Node<T>* fast=head,*slow=head;
            while(fast->next!=nullptr&&fast->next->next!=nullptr){
                slow=slow->next;
                fast=fast->next->next;
            }
            //右半边
            Node<T>* right=slow->next;
            //断链
            slow->next=nullptr;
            head=mergeSort(head);
            right=mergeSort(right);
            //归并
            return merge(head,right);
        }
        /**
         * 快排辅助函数
         * @param head 链表
         * @param tail 链表最后一个节点的下一个
         */
        static void quickSortHelper(Node<T>* head,Node<T>* tail){
            //空链表或者只有一个元素
            if(head==tail||head->next==tail){
                return;
            }
            Node<T>* p=head;//小于哨兵的节点的最后一个
            int val=head->data;//哨兵
            for(Node<T>* q=head->next;q!=tail;q=q->next){
                if(q->data<val){
                    p=p->next;
                    if(p!=q){
                        swap(p->data,q->data);
                    }
                }
            }
            swap(head->data,p->data);
            quickSortHelper(head,p);
            quickSortHelper(p->next,tail);
        }
        /**
         * 快排
         * @param head 链表
         * @return 排序后的链表
         */
        static Node<T>* quickSort(Node<T>* head){
            //空链表或者只有一个元素
            if(head==nullptr||head->next==nullptr)return head;
            quickSortHelper(head,nullptr);
            return head;
        }
    public:
        LinkedList():head(nullptr){}
        /**
         * 销毁链表
         */
        void destroy(){
            while(head!=nullptr){
                Node<T>* p=head->next;
                delete head;
                head=p;
            }
            head=nullptr;
        }
        ~LinkedList(){
            destroy();
        }
        void init(const vector<T>& init_data){
            destroy();
            Node<T>* tail= nullptr;
            for(const T& c:init_data){
                if(tail!=nullptr){
                    tail->next=new Node<T>(c);
                    tail=tail->next;
                }
                else{
                    head=tail=new Node<T>(c);
                }
            }
        }
        explicit LinkedList(const vector<T>& init_data){
            head= nullptr;
            init(init_data);
        }
        /**
         * 判断链表是否有序
         * @return true是|false否
         */
        bool isSorted()const{
            if(head==nullptr||head->next==nullptr)return true;
            T pre=head->data;
            for(Node<T>* p=head->next;p!=nullptr;p=p->next){
                if(p->data<pre)return false;
                pre=p->data;
            }
            return true;
        }
        /**
         * 选择排序
         */
        void selectSort(){
            if(head==nullptr||head->next==nullptr){
                return;
            }
            auto temp=new Node<T>();
            temp->next=head;
            for(Node<T>* r=temp;r->next->next!=nullptr;r=r->next){
                Node<T>* p,*q;
                for(p=r,q=r->next;q->next!=nullptr;q=q->next){
                    if(q->next->data<p->next->data){
                        p=q;
                    }
                }
                q=p->next;
                p->next=q->next;
                q->next=r->next;
                r->next=q;
            }
            head=temp->next;
            delete temp;
        }
        /**
         * 插入排序
         */
        void insertSort(){
            if(head==nullptr||head->next==nullptr){
                return;
            }
            auto* temp=new Node<T>();//创建一个头结点
            temp->next=head;
            Node<T>* p=head->next;
            head->next=nullptr;
            while(p!=nullptr){
                Node<T>* q=temp;
                T val=p->data;
                while(q->next!=nullptr&&q->next->data<=val){
                    q=q->next;
                }
                Node<T>* r=p->next;
                p->next=q->next;
                q->next=p;
                p=r;
            }
            head=temp->next;
            delete temp;
        }
        /**
         * 归并排序
         */
        void mergeSort(){
            head=mergeSort(head);
        }
        /**
         * 快速排序
         */
        void quickSort(){
            head=quickSort(head);
        }
        /**
         * 将链表转成vector
         * @return 转换后的vector
         */
        vector<T> getElements()const{
            vector<T> result;
            for(Node<T>* p=head;p!=nullptr;p=p->next){
                result.push_back(p->data);
            }
            return result;
        }
        friend ostream& operator<<(ostream& out,const LinkedList<T>& linkedList) {
            if(linkedList.head==nullptr){
                return out;
            }
            bool flag=false;
            for(Node<T>* p=linkedList.head;p!=nullptr;p=p->next){
                if(flag){
                    out<<' ';
                }
                else{
                    flag=true;
                }
                out<<p->data;
            }
            return out;
        }
    };
    bool isSame(vector<int>& a,vector<int>& b){
        if(a.size()!=b.size())return false;
        for(int i=0,size=a.size();i<size;++i){
            if(a[i]!=b[i])return false;
        }
        return true;
    }
    int main(){
        const int N=1000;
        random_device rd;
        vector<int> v;
        for(int i=0;i<N;++i){
            v.push_back(rd());
        }
        vector<int> temp=v;
        sort(v.begin(),v.end());
        vector<int> p;
        LinkedList<int> linkedList;
        bool flag=false;
    
        linkedList.init(temp);
        linkedList.selectSort();
        p=linkedList.getElements();
        if(!isSame(v,p)){
            cout<<"selectSort wrong"<<endl;
            flag=true;
        }
    
        linkedList.init(temp);
        linkedList.insertSort();
        p=linkedList.getElements();
        if(!isSame(v,p)){
            cout<<"insertSort wrong"<<endl;
            flag=true;
        }
    
        linkedList.init(temp);
        linkedList.mergeSort();
        p=linkedList.getElements();
        if(!isSame(v,p)){
            cout<<"mergeSort wrong"<<endl;
            flag=true;
        }
    
        linkedList.init(temp);
        linkedList.quickSort();
        p=linkedList.getElements();
        if(!isSame(v,p)){
            cout<<"quickSort wrong"<<endl;
            flag=true;
        }
        if(flag){
            for(int& c:temp){
                cout<<c<<' ';
            }
            cout<<endl;
        }
        else{
            cout<<"SUCCESS"<<endl;
        }
    
        return 0;
    }

     

    展开全文
  • 链表排序python

    千次阅读 2022-01-14 09:22:03
    而对于链表排序而言,因为链表不支持随机访问,访问链表后面的节点只能依靠next指针从头部顺序遍历,所以相对于数组排序问题来说,链表排序问题会更加复杂一点。 下面来总结一下适合链表排序与不适合链表排序的算法...

    此文章是跟DataWhale开源组织刷leetcode算法题时所写,主要内容借鉴算法通关手册

    1.链表排序简介

    在数组排序中,常见的排序算法有:冒泡,选择,插入,希尔,归并,快速,堆,计数,桶,基数排序等
    而对于链表排序而言,因为链表不支持随机访问,访问链表后面的节点只能依靠next指针从头部顺序遍历,所以相对于数组排序问题来说,链表排序问题会更加复杂一点。

    下面来总结一下适合链表排序与不适合链表排序的算法:

    • 适合链表的排序算法:冒泡,选择,插入,归并,快速,计数,桶,基数排序
    • 不适合链表的排序算法:希尔排序
    • 可以用于链表排序但不建议使用的排序算法:堆排序

    希尔排序为什么不适合链表排序?

    什么是希尔排序?
    在这里插入图片描述

    希尔排序:希尔排序中经常涉及到对序列中第i + gap的元素进行操作,其中gap是希尔排序中当前的步长。而链表不支持随机访问的特性,导致这种操作不适合链表,因而希尔排序算法不适合进行链表排序

    为什么不建议使用堆排序

    堆排序:堆排序所使用的最大堆/最小堆结构本质上是一颗完全二叉树。而完全二叉树适合采用顺序存储结构(数组)。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点,并且可以极大限度的节省存储空间。

    而链表用在存储完全二叉树的时候,因为不支持随机访问的特性,导致其寻找节点和父亲节点会比较耗时,如果增加值向父亲节点的变量,又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。

    如果一定要对链表进行堆排序,则可以使用额外的数组空间表示堆结构。然后将链表中各节点的值依次添加入堆结构中,对数组进行堆排序。排序后,再按照堆中元素顺序,依次建立链表节点,构建新的链表并返回新链表头节点。

    需要用到额外的辅助空间进行排序的算法
    刚才我们说到如果一定要对链表进行堆排序,则需要使用额外的数组空间。除此之外,计数排序,桶排序,基数排序都需要用到额外的数组空间。
    接下来,我们将对适合链表排序的8种算法进行一一讲解。当然,这些排序算法不用完全掌握,重点掌握【链表插入排序】,【链表归并排序】这两种排序算法。

    2.链表冒泡排序

    2.1 链表冒泡排序算法描述

    1. 使用node_inode_jtail。其中node_i用于控制外循环次数,循环次数为链节点个数(链表长度)。node_jtail用于控制内循环次数和循环结束位置。
    2. 排序开始前,将node_inode_j置于头节点位置。tail指向链表末尾,即None
    3. 比较链表中相邻两个元素node_j.valnode_j.next.val的值大小,如果node_j.val > node_j.next.val,则值相互交换。否则不发生交换。然后向右移动node_j指针,直到node_j.next == tail时停止。
    4. 一次循环之后,将tail移动到node_j所在位置。相对于tail向左移动了一位。此时tail节点右侧为链表中最大的链节点。
    5. 然后移动node_i节点,并将node_j置于头节点位置。然后重复第3,4步操作。
    6. 直到node_i节点移动到链表末尾停止,排序结束。
    7. 返回链表的头节点head

    2.2 链表冒泡排序算法实现代码

    def bubbleSort(self, head: ListNode):
    	node_i = head
    	tail = None
    	# 外层循环次数为 链表节点个数
    	while node_i:
    		node_j = head
    		while node_j and node_j.next != tail:
    			if node_j.val > node_j.next.val:
    				# 交换两个节点的值
    				node_j.val, node_j.next.val = node_j.next.val, node_j.val
    				node_j = node_j.next
    		# 尾指针向前移动1位,此时尾指针右侧为排好序的链表
    		tail = node_j
    		node_i = node_i.next
    	
    	return head
    

    3.链表选择排序

    3.1 链表选择排序算法描述

    • 使用两个指针node_inode_jnode_i既可以用于控制外循环次数,又可以作为当前未排序链表的第一个链节点位置。
    • 使用min_node记录当前未排序链表中值最小的链节点。
    • 每一趟排序开始时,先令min_node = node_i(即暂时假设链表中node_i节点为值最小的节点,经过比较后再确定最小值节点位置)。
    • 然后依次比较未排序链表中node_j.valmin_node.val的值大小。如果node_j.val < min_node.val,则更新min_nodenode_j
    • 这一趟排序结束时,未排序链表中最小值节点为min_node,如果node_i != min_node,则不用交换。
    • 排序结束后,继续向右移动node_i,重复上述步骤,在剩余未排序链表中寻找最小的链节点,并与node_i进行比较和交换,直到node_i == None或者node_i.next == None时,停止排序。
    • 返回链表的头结点head

    3.2 链表选择排序实现代码

    def sectionSort(self, head: ListNode):
    	node_i = head
    	# node_i 为当前未排序链表的第一个链表结点
    	while node_i and node_i.next:
    		# min_node 为未排序链表中的值最小节点
    		min_node = node_i
    		node_j = node_i.next
    		while node_j:
    			if node_j.val < min_node.val:
    				min_node = node_j
    			node_j = node_j.next
    		# 交换值最小节点与未排序链表中第一个节点的值
    		if node_i != min_node:
    			node_i.val, min_node.val = min_node.val, node_i.val
    		node_i = node_i.next
    	
    	return head
    

    4.链表插入排序

    4.1 链表插入排序算法描述

    1. 先使用哑节点dummy_head构造一个值向head的指针,使得可以从head开始遍历。
    2. 维护sorted_list为链表的已排序部分的最后一个节点,初始时,sorted_list = head
    3. 维护prev为插入元素位置的前一个节点,维护cur为待插入元素。初始时,prev = head,cur = head.next
    4. 比较sorted_listcur的节点值。
      • 如果sorted_list.val <= cur.val,说明cur应该插入到sorted_list之后,则将sorted_list后移一位。
      • 如果sorted_list.val > cur.val,说明cur应该插入到headsorted_list之间。则使用prevhead开始遍历,直到找到插入cur的位置的前一个节点位置,然后将cur插入。
    5. cur = sorted_list.next,此时cur为下一个待插元素。
    6. 重复4、5步骤,直到cur遍历结束为空。返回dummy_head的下一个节点。

    4.2 链表插入排序实现代码

    def insertionSort(self, head: ListNode):
    	if not head and not head.next:
    		return head
    	
    	dummy_head = ListNode(-1)
    	dummy_head.next = head
    	sorted_list = head
    	cur = head.next
    
    	while cur:
    		if sorted_list.val <= cur.val:
    			# 将 cur 插入到 sorted_list之后
    			sorted_list = sorted_list.next
    		else:
    			prev = dummy_head
    			while prev.next.val <= cur.val:
    				prev = prev.next
    			# 将 cur 到链表中间
    			sorted_list.next = cur.next
    			cur.next = prev.next
    			prev.next = cur
    		cur = sorted_list.next
    
    	return dummy_head.next
    

    5.链表归并排序

    5.1 链表归并排序算法描述

    • 分割环节:找到链表中心链节点,从中心节点将链表断开,并递归进行分割。

      • 使用快慢指针fast = head.nextslow = head, 让fast每次移动2步,slow移动1步,移动到链表末尾,从而找到链表中心链节点,即slow
      • 从中心位置将链表从中心位置分为左右链表left_headright_head,并从中心位置将其断开,即slow.next = None
      • 对左右两个链表分别进行递归分割,直到每个链表中包含一个链节点。
    • 归并环节:将递归后的链表进行两两归并,完成一遍后每个子链表长度加倍。重新进行归并操作,直到得到完整的链表。

      • 使用哑节点dummy_head构造一个头节点,并使用cur值向dummy_head用于遍历。
      • 比较两个链表头节点leftright的值大小。将较小的头节点加入到合并的链表中。并向后移动该链表的头节点指针。
      • 然后重复上一步操作,直到两个链表中出现链表为空的情况。
      • 将剩余链表插入到合并中的链表中。
      • 将哑节点dummy_dead的下一个链节点dummy_head.next作为合并后的头节点返回。

    5.2 链表归并排序实现代码

    def merge(self, left, right):
    	# 归并环节
    	dummy_head = ListNode(-1)
    	cur = dummy_head
    	while left and right:
    	if left.val <= right.val:
    		cur.next = left
    		left = left.next
    	else:
    		cur.next = right
    		right = right.next
    	cur = cur.next
    
    	if left:
    		cur.next = left
    	elif right:
    		cur.next = right
    
    	return dummy_head.next
    
    def mergeSort(self, head: ListNode):
    	# 分割环节
    	if not head or not head.next:
    		return head
    	
    	# 快慢指针找到中心链节点
    	slow, fast = head, head.next
    	while fast and fast.next:
    		slow = slow.next
    		fast = fast.next.next
    
    	# 断开左右链节点
    	left_head, right_head = head, slow.next
    	slow.next = None
    
    	# 归并操作
    	return self.merge(self.mergeSort(left_head), self.mergeSort(right_head))
    

    6.链表快速排序

    6.1 链表快速排序算法描述

    • 从链表中找到一个基准值pivot,这里以头节点为基准值。
    • 然后通过快慢指针node_jnode_j在链表中移动,使得node_i之前的节点值都小于基准值,node_i之后的节点值都大于基准值。从而把数组拆分为左右两个部分。
    • 再对左右两个部分分别重复第二步,直到各个部分只有一个节点,则排序结束。

    6.2 链表快速排序实现代码

    def partition(self, left: ListNode, right: ListNode):
    	# 左闭右开,区间没有元素或者只有一个元素,直接返回第一个节点
    	if left == right or left.next == right:
    		return left
    	# 选择头节点为基准节点
    	pivot = left.val
    	# 使用node_i,node_j双指针,保证node_i之前的节点都小于基准节点值,node_i与node_j之间的节点值都大于等于基准节点值
    	node_i, node_j = left, left.next
    
    	while node_j != right:
    		# 发现一个小于基准值的元素
    		if node_j.val < pivot:
    			# 因为 node_i 之前节点都小于基准值,所以先将node_i向右移动一位(此时node_i节点大于等于基准节点值)
    			node_i = node_i.next
    			# 将小于基准值的元素 node_j 与当前node_i换位,换位后可以保证node_i之前的节点都小于基准节点值
    			node_i.val, node_j.val = node_j.val, node_i.val
    		node_j = node_j.next
    	# 将基准节点放到正确位置上
    	node_i.val, left.val = left.val, node_i.val
    	return node_i
    
    def quickSort(self, left:ListNode, right: ListNode):
    	if left == right or left.next == right:
    		return left
    	pi = self.partition(left, right)
    	self.quickSort(left, pi)
    	self.quickSort(pi.next, right)
    	return left
    

    7.链表计数排序

    7.1 链表计数算法描述

    • 使用cur指针遍历一遍链表。找出链表中最大值list_max和最小值list_min
    • 使用数组counts存储节点出现次数。
    • 再次使用cur指针遍历一遍链表。将链表中每个值为cur.val的节点出现次数,存入数组对应第cur.val - list_min项中。
    • 反向填充目标链表:
      • 建立一个哑节点dummy_head,作为链表的头节点,使用cur指针值向dummy_head
      • 从小到大遍历一遍数组counts。对于每个counts[i] != 0的元素建立一个链节点,值为i + list_min,将其插入到cur.next上。并向右移动cur。同时counts[i] -= 1。直到counts[i] == 0后继续向后遍历数组counts
      • 将哑节点dummy_dead的下一个链节点dummy_head.next作为新链表的头节点返回。

    7.2 链表计数排序代码实现

    def countingSort(self, head: ListNode):
    	if not head:
    		return head
    	
    	# 找出链表中最大值list_max和最小值list_min
    	list_min, list_max = float('inf'), float('-inf')
    	cur = head
    	while cur:
    		if cur.val < list_min:
    			list_min = cur.val
    		if cur.val > list_max:
    			list_max = cur.val
    		cur = cur.next
    	
    	size = list_max - list_min + 1
    	counts = [0 for _ in range(size)]
    
    	cur = head
    	while cur:
    		counts[cur.val - list_min] += 1
    		cur = cur.next
    	
    	dummy_head = ListNode(-1)
    	cur = dummy_head
    	for i in range(size):
    		while counts[i]:
    			cur.next = ListNode(i + list_min)
    			counts[i] -= 1
    			cur = cur.next
    	return dummy_head.next
    

    8.链表桶排序

    8.1 链表桶排序算法描述

    • 使用cur指针遍历一遍链表。找出链表中最大值list_max和最小值list_min
    • 通过(最大值 - 最小值) / 每个桶的大小计算出桶的个数,即bucket_count = (list_max - list_min) // bucket_size + 1个桶。
    • 定义二维数组buckets为桶,外层数组大小为bucket_count个。
    • 使用cur指针再次遍历一遍链表,将每个元素装入对应的桶中。
    • 对每个桶内元素单独排序(使用插入、归并、快排等算法)。
    • 最后按照顺序将桶内的元素拼成新的链表,并返回。

    8.2 链表桶排序代码实现

    def insertionSort(self, arr):
    	for i in range(1, len(arr)):
    		temp = arr[i]
    		j = i
    		while j > 0 and arr[j - 1] > temp:
    			arr[j] = arr[j - 1]
    			j -= 1
    		arr[j] = temp
    
    	return arr
    
    def bucketSort(self, head: ListNode, bucket_size = 5):
    	if not head:
    		return head
    
    	# 找出链表中最大值list_max 和最小值 list_min
    	list_min, list_max = float'inf'), float('-inf')
    	cur = head
    	while cur:
    		if cur.val < list_min:
    			list_min = cur.val
    		if cur.val > list_max:
    			list_max = cur.val
    		
    		cur = cur.next
    	
    	# 计算桶的个数,并定义桶
    	bucket_count = (list_max - list_min) // bucket_size + 1
    	buckets = [[] for _ in range(bucket_count)]
    
    	# 将链表节点依次添加到对应桶中
    	cur = head
    	while cur:
    		buckets[(cur.val - list_min) // bucket_size].append(cur.val)
    		cur = cur.next
    
    	dummy_head = ListNode(-1)
    	cur = dummy_head
    	for bucket in buckets:
    		# 对桶中元素单独排序
    		self.sortLinkedList(bucket)
    		for num in bucket:
    			cur.next = ListNode(num)
    			cur = cur.next
    
    	return dummy_head.next
    

    9. 链表基数排序

    9.1 链表基数排序算法描述

    • 使用cur指针遍历,获取节点位数最长的位数size
    • 从个位到高位遍历位数。因为0-9共有10位数字,使用建立10个桶。
    • 以每个节点对应数上的数字为索引,将节点值放入到对应桶中。
    • 建立一个哑节点dummy_head,作为链表的头节点。使用cur指针指向dummy_head
    • 将桶中元素依次取出,并根据元素值建立链表节点,并插入到新的链表后面。从而生成新的链表。
    • 之后依次以十位,百位,…,直到最大值元素的最高位处值为索引,放入到对应桶中,并生成新的链表,最终完成排序。
    • 将哑节点dummy_dead的下一个链节点dummy_head.next作为新链表的头节点返回。

    9.2 链表基数排序代码实现

    def radixSort(self, head: ListNode):
    	# 计算位数最长的位数
    	size = 0
    	cur = head
    	while cur:
    		val_len = len(str(cur.val))
    		if val_len > size:
    			size = val_len
    		cur = cur.next
    
    	# 从个位到高位遍历位数
    	for i in range(size):
    		buckets = [[] for _ in range(10)]
    		cur = head
    		while cur:
    			# 以每个节点对应位数上的数字为索引,将节点值放入到对应桶中
    			buckets[cur.val // (10 ** i) % 10].append(cur.val)
    			cur = cur.next
    
    	# 生成新的链表
    	dummy_head = ListNode(-1)
    	cur = dummy_head
    	for bucket in buckets:
    		for num in bucket:
    			cur.next = ListNode(num)
    			cur = cur.next
    	head = dummy_head.next
    
    return head
    
    展开全文
  • 主要介绍了JavaScript实现链表插入排序链表归并排序,较为详细的分析了插入排序和归并排序,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下。
  • 实验内容 使用链表实现下面各种排序算法并进行比较 排序算法 1插入排序 2 冒泡排序改进型冒泡排序 3快速排序 4 简单选择排序 5堆排序小根堆 要求 1测试数据分成三类正序逆序随机数据 2 对于这三类数据比较上述排序...
  • #资源达人分享计划#
  • C语言链表排序操作

    2017-06-29 13:41:43
    链表创建、排序操作
  • 【算法专题】链表排序算法总结

    千次阅读 2021-10-24 15:41:55
    链表排序算法总结 概述 问题描述:给定一个链表,请将这个链表升序排列。 节点定义: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 1 链表插入排序 题目描述...

    链表排序算法总结

    概述

    
    问题描述:给定一个链表,请将这个链表升序排列。
    
    
    • 节点定义:
    struct ListNode {
        int val;
        ListNode *next;
    
        ListNode(int x) : val(x), next(NULL) {}
    };
    

    1 链表插入排序

    题目描述:Leetcode 0147 链表进行插入排序

    在这里插入图片描述

    分析

    • 因为头结点可能会改变,因此需要设置一个虚拟头结点dummy

    • 我们从前向后遍历整个链表,假设当前考察节点为p,我们需要从dummy开始遍历,找到第一个大于p->val的前一个节点cur,然后将p插入到cur后面。

    代码

    • C++
    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            auto dummy = new ListNode(-1);
            for (auto p = head; p; ) {
                auto cur = dummy, next = p->next;  // next是下一个需要考察的节点
                while (cur->next && cur->next->val <= p->val) cur = cur->next;
                p->next = cur->next;
                cur->next = p;
                p = next;
            }
            return dummy->next;
        }
    };
    

    时空复杂度分析

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)n为链表长度。

    • 空间复杂度: O ( 1 ) O(1) O(1)

    2 链表归并排序

    题目描述:Leetcode 0148 排序链表

    在这里插入图片描述

    分析

    • 因为要求时间O(1),因此就不能使用递归的写法,这一题可以使用归并排序的迭代写法(自底向上)。

    • 这一题十分类似于Leetcode 0023 合并K个有序链表,我们可以使用LC23的思路求解。代码中的变量如下图所示:

    在这里插入图片描述

    • 上面的做法用C++演示。

    • Java演示一下递归(自顶向下)的写法,但是空间复杂度不是 O ( 1 ) O(1) O(1)的。关键在于找到链表的中点,与Leetcode 0109 将有序链表转换二叉搜索树类似,这两题都需要找到中点,不同于LC109,LC109的终止条件是f != null && f->next != null,这里使用的终止条件是f.next != null && f->next->next != null,两者的区别为:

    在这里插入图片描述

    代码

    • C++
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            int n = 0;
            for (auto p = head; p; p = p->next) n++;  // 求出节点数目
    
            for (int len = 1; len < n; len += len) {  // 枚举合并长度
                // 下面循环一次代表向上递推一层
                auto dummy = new ListNode(-1), cur = dummy;  // 因为头结点可能变,因此需要虚拟头结点
                for (int j = 1; j <= n; j += 2 * len) {  // 枚举待合并链表的起点, j不会再下面用到
                    auto p = head, q = head;
                    for (int i = 0; i < len && q; i++) q = q->next;
                    auto o = q;  // o为下次合并的起点
                    for (int i = 0; i < len && o; i++) o = o->next;
                    // 归并p、q开头的链表
                    int l = 0, r = 0;
                    while (l < len && r < len && p && q)    
                        if (p->val <= q->val) cur = cur->next = p, p = p->next, l++;
                        else cur = cur->next = q, q = q->next, r++;
                    while (l < len && p) cur = cur->next = p, p = p->next, l++;
                    while (r < len && q) cur = cur->next = q, q = q->next, r++;
                    head = o;  // 进行后面两段链表的合并
                }
                cur->next = NULL;
                head = dummy->next;
            }
            return head;
        }
    };
    
    • Java
    class Solution {
        public ListNode merge(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            if (l1.val < l2.val) {
                l1.next = merge(l1.next, l2);
                return l1;
            } else {
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }
    
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            // 快慢指针,寻找中间点
            ListNode s = head, f = head;
            while (f.next != null && f.next.next != null) {
                s = s.next; f = f.next.next;
            }
            ListNode newHead = s.next;
            s.next = null;  // 断开链表,分成前后两部分
    
            ListNode left = sortList(head), right = sortList(newHead);
            return merge(left, right);  // 返回合并后的链表头指针
        }
    }
    

    时空复杂度分析

    • 时间复杂度: O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))n为链表长度。

    • 空间复杂度:C++ O ( 1 ) O(1) O(1)Java O ( l o g ( n ) ) O(log(n)) O(log(n))

    3 链表快速排序

    题目描述:AcWing 1451. 单链表快速排序

    在这里插入图片描述

    分析

    • 使用三个虚拟头指针left, mid, right,记录每次partition的结果,这里取头结点val的值作为分界线。

    • 递归的过程中,我们每次都要遍历整个链表,对节点值小于val的节点接到left中,节点值等于val的节点接到mid中,节点值大于val的节点接到right中,之后还要将三个链表的尾结点置为空。

    • 接着递归处理left、right,递归结束后将三段拼接起来即可。

    代码

    • C++
    class Solution {
    public:
        ListNode* quickSortList(ListNode* head) {
            
            if (!head || !head->next) return head;
            
            auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
            auto ltail = left, mtail = mid, rtail = right;
            int val = head->val;
            
            for (auto p = head; p; p = p->next) {
                if (p->val < val) ltail = ltail->next = p;
                else if (p->val == val) mtail = mtail->next = p;
                else rtail = rtail->next = p;
            }
            
            ltail->next = mtail->next = rtail->next = NULL;
            left->next = quickSortList(left->next);
            right->next = quickSortList(right->next);
            
            // 拼接三个链表
            get_tail(left)->next = mid->next;
            get_tail(mid)->next = right->next;
            
            auto p = left->next;
            
            delete left;
            delete mid;
            delete right;
            
            return p;
        }
        
        // 获取链表的尾节点
        ListNode* get_tail(ListNode* head) {
            while (head->next) head = head->next;
            return head;
        }
    };
    

    时空复杂度分析

    • 时间复杂度: O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))n为链表长度。

    • 空间复杂度: O ( l o g ( n ) ) O(log(n)) O(log(n))

    展开全文
  • 链表排序总结(全)(C++)

    千次阅读 多人点赞 2020-07-18 15:17:48
    文章目录链表排序与数组排序的区别借助外部空间冒泡排序插入排序归并排序快速排序 链表排序与数组排序的区别 数组的排序几乎所有人都很熟悉了,常用的算法插入、冒泡、归并以及快排等都会或多或少依赖于数组可以在O...
  • 经典的双向链表排序算法。涵盖创建,删除,排序,获取,增加等
  • js的链表排序

    2021-06-29 22:18:29
    js链表排序 链表数据交换的心得 假如通过两个地址进行交换节点内容时,也应当将我们的next来进行交换赋值, 或者可以不改动我们的next,通过定义数据的中间量来将我们的数据进行改变 通过while循环找到我们想...
  • 双向链表排序 c++

    2021-11-24 22:19:55
    双向链表排序 c++ #include <iostream> using namespace std; //节点类型的定义 typedef struct node { int data; node *pre; node *next; node(int _data) : data(_data), pre(NULL), next(NULL) { } ...
  • 在VC,建立单链表,输入链表数据,搜索链表数据,插入新链表元素。实现输入数据的排序和输出。
  • C 单向链表排序

    2021-09-06 11:22:40
    链表排序链表排序的两种方式一、交换结点的数据域二、断开链表,重新形成方法示例 链表排序的两种方式 一、交换结点的数据域 有很多种方法,比如冒泡排序,选择排序等其他排序方法 struct Node *link_sort(struct ...
  • C++链表排序(归并法+快速排序)

    千次阅读 2021-04-18 22:16:34
    链表归并排序的过程如下。 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表...
  • c++链表排序

    千次阅读 2021-03-17 10:45:18
    } //链表冒泡排序 void bubbleSort(stulist &head) { stulist p,pre, tail; tail = NULL; while(head -> next != tail) { pre = head; p = head -> next; while(p -> next != tail) { cout<Major<<" "<next->Major,...
  • 链表排序算法(Java实现)

    千次阅读 2020-11-22 21:04:13
    对链表进行插入排序,是最简单的一种链表排序算法,用于插入排序是迭代的,所以每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。        每次迭代中,插入排序只从输入数据中移...
  • 链表排序java实现

    2021-11-24 23:47:44
    } //返回第二个链表的头节点 ListNode second = slow.next; slow.next = null; return second; } public ListNode merge(ListNode head1,ListNode head2){ //哨兵节点 ListNode dummy = new ListNode(0); ListNode ...
  • lianbiao.rar_链表 排序

    2022-09-19 13:40:22
    链表进行排序 应用了多种排序方法 对其进行比较 有自己的详细的时间函数
  • 链表排序【C语言】

    千次阅读 2022-03-28 20:09:39
    插入排序 #include<stdio.h> #include<stdlib.h> int n; typedef struct LinkList{ int val; struct LinkList *next; }LNode; LNode* InsertionSort(LNode* head) { if(head==NULL||head->next=...
  • 用c语言实现链表排序,利用选择排序的思想,可以供大家学习。
  • C语言链表排序

    2014-10-08 09:21:03
    C语言 链表排序,源代码,代码清晰,适合初学者下载
  • 链表排序的快排实现

    千次阅读 2022-03-10 15:51:25
    链表快排思路及代码
  • 题目: 给定链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 输入:head = [4,2,1,3] 输出:[1,2,3,4] 输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5] 分析: 代码:
  • C/C++ 编写函数,通过输入单向链表的头指针,对链表的value进行排序,返回排序后单向链表的头指针
  • c语言 整数链表排序

    2010-08-05 13:20:18
    整数链表排序的c源代码 说明:试按以下给出的排序算法为整数链表编写一个排序函数: 该算法是按表元键值的各位值进行排序。 设有一个整数链表,其中表元的键值为不超过三位数的整数,不妨设键值形式ABC。其中A...
  • 1. 对链表进行插入排序(力扣:147) 2. 排序链表(力扣:148) Java实现
  • 用双链表实现链表的合并以及链表的排序,其中包括链表的一些基本操作也有用于链表排序,链表合并的函数

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 294,285
精华内容 117,714
关键字:

链表排序