4. sort-list 链表排序

阳光穿透心脏的1/2处 2022-06-06 13:58 194阅读 0赞

## 题目描述 ##

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

单向链表排序，要求时间复杂度为*O*(*n* log *n*)，空间复杂度为O(1)。

## 题目解析 ##

第一次看到链表排序，往往链表在插入的时候就已经排序好了，不需要写额外的排序的程序。

既然是排序，总也离不开排序算法，像冒泡排序、堆排序、归并排序、快速排序等。但排序算法往往是数组的排序，所以先简单说一下链表和数组的不同。

链表这个结构就是插入和删除时要比数组要快很多（因为数组插入和删除元素后需要移位很多个格子），但是取值比数组要麻烦的多，链表需要遍历链表去取值，所以这个题的难点在于如何去索引到需要的节点。

用链表比较好实现的排序算法有**冒泡排序**和**归并排序**（Note:往下看需要先明白冒泡排序和归并排序），显然归并排序是满足题目要求的时间复杂度和空间复杂度的。

**方法一：**

利用**冒泡排序**（当然这个的时间复杂度没有O(nlogn)）去做链表的排序，利用记录最后一个节点last去记录遍历到哪一次循环了，每遍历一次，last确定一个并往前移动一次，直到last移动到head，说明每个node的顺序都确定好，遍历结束。

代码如下：

void swapListVal(ListNode *node1, ListNode *node2)
        {
            if (NULL == node1 || NULL == node2) return ;
            
            int tmp = node1->val;
            node1->val = node2->val;
            node2->val = tmp;
        }
        
        ListNode *sortList(ListNode *head) 
        {
            ListNode *last = NULL;
            ListNode *cur = head;
            
            while (last != head)
            {
                cur = head;
                while (cur->next != last)
                {
                    if (cur->next->val < cur->val) 
                        swapListVal(cur, cur->next);
                    
                    cur = cur->next;
                }
                
                last = cur;
            }
            
            return head;
        }

**方法二：**

利用**归并****排序**去对链表进行排序，利用递归方法去实现

**快慢指针**实现 找到中间位置的指针

链表的断开与重建

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            if (!head || !head->next) return head;
             
            ListNode* p = head, *q = head->next;
            while(q && q->next) {
                p = p->next;
                q = q->next->next;
            }
             
            ListNode* right = sortList(p->next);
            p->next = NULL;
            ListNode* left = sortList(head);
             
            return merge(left, right);
        }
         
         
        ListNode *merge(ListNode *left, ListNode *right) {
            ListNode dummy(0);
            ListNode *p = &dummy;
            while(left && right) {
                if(left->val < right->val) {
                    p->next = left;
                    left = left->next;
                }
                else {
                    p->next = right;
                    right = right->next;
                }
                p = p->next;
            }
            if (left) p->next = left; if (right) p->next = right;
            return dummy.next;
        }
    };