首页 > 代码库 > leetcode Sort List
leetcode Sort List
实现链表的nlgn时间排序，常数空间。
想了想，符合那个时间复杂度的也就快排，堆，归并。一想到快排的最坏也是n方，就放弃了，堆的话貌似起码要组成堆要左右两个指针构建才比较方便。然后就觉得应该是要用归并了。
还是看了JustDOIT大神的。自己也敲了一下。
利用快慢指针找到中间，分成两个链表，然后递归，然后合并。如下：
/** * 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 *fast = head, *slow = head; while(fast -> next && fast -> next -> next) { fast = fast -> next -> next; slow = slow -> next; } fast = slow; slow = slow -> next; fast -> next = NULL; fast = sortList(head); slow = sortList(slow); return mergeList(fast, slow); } ListNode *mergeList(ListNode *l1, ListNode *l2) { if (!l1) return l2; if (!l2) return l1; ListNode *pre = new ListNode (0); ListNode *mer = pre; while(l1 && l2) { if (l1 -> val < l2 -> val) { mer -> next = l1; l1 = l1 -> next; mer = mer -> next; } else { mer -> next = l2; l2 = l2 -> next; mer = mer -> next; } } if (l1) mer -> next = l1; if (l2) mer -> next = l2; mer = pre -> next; delete pre; return mer; }};
但是上面的不符合常数空间。常数空间的就直接贴了：
//非递归，空间复杂度为常量/** * 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 == NULL) return head; ListNode *leftList, *rightList, *tail, *temp; //每次归并的次数,当归并次数为1时则表示没有进行归并，说明归并完成 int mergeCount; int widthSize = 1; //每次归并链表的宽度,初始值为1,(2,4,8,....) int leftSize ; //左链表大小 int rightSize ; while (true) //退出条件为mergeCount = 0 { //tail指向当前已归并链表最后一个节点，每次归并开始前都要清空 //每次归并开始前leftList指向最新的head,归并次数置0 mergeCount = 0; tail = NULL; leftList = head; rightList = NULL; //每次两个链表归并完成后leftList会指向下一个段的左链表 //如果没有下一个左链表，则一次归并完成，所以以leftList //作为判断条件 while (leftList) { ++mergeCount; //每次归并的趟数，到1时表示没有归并 //找到rightList的位置,顺便算出leftSize大小 rightList = leftList; //从左链表开始向后滑动 leftSize = 0; rightSize = 0; for (int i = 0; i < widthSize; ++i) { if (rightList) { ++leftSize; rightList = rightList->next; } else //最后一个左链表不够一个区间长度，但链表已遍历完,完成查找 break; } //找到两个需要归并的链表的头结点，以及大小 rightSize = widthSize; //按最大算,判断是否遍历完时加上指针 //区间长度作为归并循环条件,归并一个区间-1，直至两个区间都排完 while (leftSize > 0 || ((rightSize > 0)&& rightList)) { //temp保存临时更小的那个节点，tail始终保存已排好的链尾 //首先要考虑一个区间是否已排完，因为如果区间已排完，leftList //或者rightList由于会后移一个单位将指向另一个区间 if (leftSize == 0) { //即((rightSize > 0)&& rightList)为真 temp = rightList; rightList = rightList->next; --rightSize; } else if (rightSize == 0 || rightList == NULL) { //leftSize不为0,注意右链表归并完rightList指针会 //移到后面，即下一个归并对的最左一个元素 temp = leftList; leftList = leftList->next; --leftSize; }//剩下的情况就是两个归并对剩余待归并元素都不为空 else if (leftList->val <= rightList->val) { temp = leftList; leftList = leftList->next; --leftSize; } else if (leftList->val > rightList->val) { temp = rightList; rightList = rightList->next; --rightSize; } //找到更小的一个元素，改变链表指向更小的元素 if (tail == NULL) { //第一个找出的元素,定头结点 head = temp; tail = temp; } else { tail->next = temp; tail = tail->next; //tail永远指向最后一个排好序的节点 } }//while (leftSize > 0 || ((rightSize > 0)&& rightList)) //一个归并对完成，前面已经提过rightList指向下一个归并对的最左节点 leftList = rightList; tail->next = leftList; }//while (leftList) tail->next = NULL; //tail指向最后一个节点，一趟归并完然后把tail的next设为空 //归并完成判断 if (mergeCount <= 1) return head; widthSize *=2; } return NULL; }
也可以到他的主页看。
leetcode Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。