链表排序算法

包括冒泡、选择、插入、快排、归并、希尔和堆排序

以下排序算法的正确性都可以在LeetCode的链表排序这一题检测。本文用到的链表结构如下（排序算法都是传入链表头指针作为参数，返回排序后的头指针）

struct ListNode {

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

插入排序（算法中是直接交换节点，时间复杂度O（n^2）,空间复杂度O（1））

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head == NULL || head->next == NULL)return head;
        ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;
        pstart->next = head; //为了操作方便，添加一个头结点
        while(p != NULL)
        {
            ListNode *tmp = pstart->next, *pre = pstart;
            while(tmp != p && p->val >= tmp->val) //找到插入位置
                {tmp = tmp->next; pre = pre->next;}
            if(tmp == p)pend = p;
            else
            {
                pend->next = p->next;
                p->next = tmp;
                pre->next = p;
            }
            p = pend->next;
        }
        head = pstart->next;
        delete pstart;
        return head;
    }
};

选择排序（算法中只是交换节点的val值，时间复杂度O（n^2）,空间复杂度O（1））

class Solution {
public:
    ListNode *selectSortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        //选择排序
        if(head == NULL || head->next == NULL)return head;
        ListNode *pstart = new ListNode(0);
        pstart->next = head; //为了操作方便，添加一个头结点
        ListNode*sortedTail = pstart;//指向已排好序的部分的尾部

        while(sortedTail->next != NULL)
        {
            ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;
            //寻找未排序部分的最小节点
            while(p != NULL)
            {
                if(p->val < minNode->val)
                    minNode = p;
                p = p->next;
            }
            swap(minNode->val, sortedTail->next->val);
            sortedTail = sortedTail->next;
        }

        head = pstart->next;
        delete pstart;
        return head;
    }
};

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 排序
， next
， null
， leetcode
， 复杂度
， head
， 链表 算法
， 链表排序算法
， 广义表head
， 复杂排序
next()
链表排序、排序算法、链表、单链表排序算法、c语言链表排序算法，以便于您获取更多的相关知识。