单链表排序

题目

题目链接

单链表的排序_牛客题霸_牛客网

题目描述

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *left = head, *mid = head->next, *right = head->next->next;
        while(right && right->next){
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        left->next = nullptr;
        return mergeList(sortInList(head), sortInList(mid));
    }
    /*合并两个有序链表*/
    ListNode* mergeList(ListNode* head1, ListNode* head2){
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;
        ListNode* phead = new ListNode(-1), *cur = phead;
        while(head1 && head2){
            if(head1->val < head2->val){
                cur->next = head1;
                head1 = head1->next;
            }
            else{
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        cur->next = head1 == nullptr ? head2 : head1;
        return phead->next;
    }
};

思路分析

单链表的缺点是不易随机访问，所以链表的排序并不能向数组那样简单。

这里我们采用归并的思想对单链表进行排序。即将单链表分割成为单个单个的节点，对于两个单个节点采用合并有序链表的思路。可以参考我的这篇博文

合并两个有序链表-CSDN博客

对于归并好的两个节点就是一个有序的链表了。然后继续向回返，仍旧归属于合并两个有序链表的范畴。

如果不熟悉归并的思想可以参考我的这篇博文

归并排序和计数排序-CSDN博客

原文地址：https://blog.csdn.net/qq_45576085/article/details/136475072

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！