排序链表（Sort linked list）

刺骨的言语ヽ痛彻心扉 2022-08-12 11:30 33阅读 0赞

Sort List

Sort a linked list in O(n log n) time using constant space complexity

分别使用快速排序和归并排序来实现，最后再用插入排序实现（ O(n^2)）。

使用快速排序的代码：

/**
     * Definition for singly-linked list.
     */
     #include 
        
         
     #include 
         
          
     using namespace std;
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        void quickSortLinkList(ListNode *begin , ListNode *end)
        {
            if(begin == end || begin->next == end)
                return;
            ListNode *i ,*j , *i_pre , *j_pre;
            int tmp;
            for(i = begin->next , i_pre = begin ; i != end ; )
            {
                if(i->val < begin->val)
                {
                    i_pre = i;
                    i = i->next;
                }
                else
                    break;
            }
            j = i;
            j_pre = i_pre;
            if(i != end)
            {
                for(i = i->next , i_pre = i_pre->next ; i != end ; )
                {
                    if(i->val >= begin->val)
                    {
                        i_pre = i;
                        i = i->next;
                    }
                    else
                    {
                        tmp = i->val;
                        i->val = j->val;
                        j->val = tmp;
                        j_pre = j;
                        j = j->next;
                        i_pre = i;
                        i = i->next;
                    }
                }
            }
            //for(i = begin ; i->next != j; i = i->next);
            i = j_pre;
            if(i != begin)
            {
                tmp = i->val;
                i->val = begin->val;
                begin->val = tmp;
                quickSortLinkList(begin, i);
                quickSortLinkList(j , end);
            }
            else
            {
                quickSortLinkList(i->next , end);
            }
        }
        ListNode *sortList(ListNode *head) {
            quickSortLinkList(head, NULL);
            return head;
        }
    };
    int main()
    {
        ListNode *head = NULL ;
        ListNode *p = NULL;
        Solution s;
        srand((unsigned)GetCurrentTime());
        int i = 50;
        while(--i >= 0)
        {
            p = head;
            head = new ListNode(rand()%4);
            head->next = p;
        }
        head = s.sortList(head);
        for(p = head; p != NULL ; p = p->next)
            cout << p->val << endl;
        return 1;
    }

虽然快速排序的时间复杂度是  O(n log n)，空间复杂度也是常量。但是交换次数过多了。

**使用归并排序的代码：**

/**
     * Definition for singly-linked list.
     */
     #include 
        
         
     #include 
         
          
     using namespace std;
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        ListNode *Merge(ListNode *a , ListNode *b)
        {
            if(a == NULL)
                return b;
            if(b == NULL)
                return a;
            ListNode *i, *j, *k ,*head;
            i = a;
            j = b;
            if((a->val) < (b->val))
            {
                head = a;
                i = a->next;
            }
            else
            {
                head = b;
                j = b->next;
            }
            k = head;
            while((i != NULL) && (j != NULL))
            {
                if(i->val > j->val)
                {
                    k->next = j;
                    j = j->next;
                    k = k->next;
                }
                else
                {
                    k->next = i;
                    i = i->next;
                    k = k->next;
                }
            }
            if(i == NULL)
                k->next = j;
            if(j == NULL)
                k->next = i;
            return head;
        }
        ListNode *sortList(ListNode *head) {
            if(head == NULL || head->next == NULL)
                return head;
            ListNode *mid, *p , *mid_pre;
            mid = head;
            p = head;
            while(p != NULL)
            {
                mid_pre = mid;
                mid = mid->next;
                p = p->next;
                if(p == NULL)
                    break;
                p = p->next;
            }
            mid_pre->next = NULL;
            head = sortList(head);
            mid = sortList(mid);
            return Merge(head, mid);
        }
    };
    int main()
    {
        ListNode *head = NULL ;
        ListNode *p = NULL;
        Solution s;
        srand((unsigned)GetCurrentTime());
        int i = 30;
        while(--i >= 0)
        {
            p = head;
            head = new ListNode(rand()%10);
            head->next = p;
        }
        head = s.sortList(head);
        for(p = head; p != NULL ; p = p->next)
            cout << p->val << endl;
        return 1;
    }

还不错。

=======================================================================

插入排序（ O(n^2)）的代码：

/**
     * Definition for singly-linked list.
     */
     #include 
        
         
     #include 
         
          
     using namespace std;
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            if(head == NULL || head->next == NULL)
                return head;
            ListNode *p, *t_pre ,*t;
            p = head->next;
            head->next = NULL;
            while(p != NULL)
            {
                t = head;
                t_pre = head;
                if((head->val) >= (p->val))
                {
                    head = p;
                    p = p->next;
                    head->next = t;
                }
                else
                {
                    while((t->val) < (p->val))
                    {
                        t_pre = t;
                        t = t->next;
                        if(t == NULL)
                            break;
                    }
                    t_pre->next = p;
                    p = p->next;
                    t_pre->next->next = t;
                }
            }
            return head;
        }
    };
    int main()
    {
        ListNode *head = NULL ;
        ListNode *p = NULL;
        Solution s;
        srand((unsigned)GetCurrentTime());
        int i = 30;
        while(--i >= 0)
        {
            p = head;
            head = new ListNode((rand()+5)%10);
            head->next = p;
        }
        head = s.insertionSortList(head);
        for(p = head; p != NULL ; p = p->next)
            cout << p->val << endl;
        return 1;
    }