148. Sort List（链表排序/O(1)空间）

快来打我* 2023-07-18 12:41 25阅读 0赞

将链表排序，但是要求不能使用额外空间。空间复杂度O（1），时间复杂度O（nlgn）。  
首先这个题很容易使用递归和分治方法，但是在递归的过程中会需要堆栈空间来存储递归函数的栈帧。递归使用的是up-to-bottom策略，在这里使用bottom-to up策略。  
思路：  
首先先将list分成两个list，然后再排序合并两个链表。  
step=1，2，4，8.。。因为分链表的时候按照step分，合在一起后变成了2step。  
虚拟的节点dummy，作为每次刚开始进行分的头节点（to 找到固定的head）。因为进行merge的 时候，这个节点作为头节点，之后tail便是已经排好序的链表的尾部（非空节点）  
split是将按照step分开链表，left是step从开始分的step个，right是从left段之后开始分的list。cur是他们两个之后还没有分的链表。  
直到最后的step>=len，才说明排序完成。

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    //思路：首先要求nlongn时间复杂度，O（1）空间复杂度，就是不能再开空间了。所以我们对链表排序：
    //通过先将链表分成两个，然后再合并两个链表的方式。
    class Solution { 
    public:
        ListNode* sortList(ListNode* head) { 
            if(!head || !(head->next))   return head;
            //获取链表的长度
            int len=0;
            ListNode* cur=head;
            while(cur)
            { 
                len++;
                cur=cur->next;
            }
            ListNode dummy(0);      //虚拟节点
            dummy.next=head;
            ListNode*left,*right,*tail;
            for(int step=1;step<len;step<<=1)       //step右移一位，
            { 
                cur=dummy.next;
                tail=&dummy;
                while(cur)          //这部分是为了按照STEP排好序
                { 
                    left=cur;
                    right=split(left,step); //left走step后开始分成两段。后一段赋值给right
                    cur=split(right,step);      //后一段赋值给cur
                    tail=merge(left,right,tail);    //这是将拆分好的两段连在一起，tail作为结尾一个非空节点。
                }       //分合
            }            
            return dummy.next;
        }
        private:
        ListNode* split(ListNode* head,int n)
        { 
            for(int i=1;head&& i<n; ++i)
                    head=head->next;        //走的步数
            if(!head)
                return nullptr;
            ListNode* second=head->next;
            head->next=nullptr;
            return second;          //被分段后的第一个节点
        }
        
        //分之后是合:输入两个节点，和一个头节点。进行链表连接，返回最后一个节点！
        ListNode* merge(ListNode* l1,ListNode* l2,ListNode* head)
        { 
            ListNode *cur=head;
            while(l1&&l2)
            { 
                if(l1->val  >  l2->val)
                { 
                    cur->next=l2;
                    cur=l2;
                    l2=l2->next;
                }
                else
                { 
                    cur->next=l1;
                    cur=l1;
                   l1= l1->next;
                }
            }
            //连完了有一个到nullptr
            cur->next=(l1? l1:l2);
            while(cur->next)    cur=cur-> next;
            return cur;
        }   
    };