148.排序链表
1.题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
2.解题报告
针对nlogn的排序算法，主要有快速排序，归并排序和堆排序。其中，堆排序利用了数组的连续特性。所以这里不能采用。其次，在快速排序中，设计大量数字的交换且单链表因为只能单向遍历，使用partition不是很直观。
所以，本题采用归并排序链表版来实现。
具体思路如下：
1.使用快慢指针，找到链表的中点。
2.对链表的前半部分和后半部分分别排序。
3.将两部分合并。
代码
/*** 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) {return sortList(head, NULL);}private:// sort [beg, end), and return new head, and tail->next = end;ListNode* sortList(ListNode*beg, ListNode* end) {if (beg == end || !beg || beg->next == end) {return beg;}// at least has two node// [head, mid, end], maybe head == mid == end// [head, mid) < mid < [mid->next, end)ListNode* head = NULL; // new headListNode* mid = NULL;beg = partition(beg, end, &head, &mid);// sort [mid->next, end)if (mid && mid->next != end) {mid->next = sortList(mid->next, end);}// sort [head, mid)return sortList(head, mid);}ListNode* partition(ListNode* beg, ListNode* end,ListNode** p_head, ListNode** p_mid) {if (!beg || !p_head || !p_mid) {return beg;}ListNode* mid = beg;ListNode* tail1 = NULL;ListNode* tail2 = NULL;int v = mid->val;ListNode* p = mid->next;while (p != end) {if (p->val < v) {if (!*p_head) {*p_head = p;tail1 = p;} else {tail1->next = p;tail1 = p;}} else {if (!tail2) {mid->next = p;tail2 = p;} else {tail2->next = p;tail2 = p;}}p = p->next;}if (tail1) {tail1->next = mid; }else {*p_head = mid; }if (tail2) {tail2->next = end; }else {mid->next = end; }*p_mid = mid;return *p_head;}};
3. 最佳答案
c答案
/*** Definition for singly-linked list.* struct ListNode {*int val;*struct ListNode *next;* };*///head不参与排序！void mergeSortList(struct ListNode* head) {struct ListNode* slow, *fast,*pre;if (NULL == head)return;//无效输入else{struct ListNode R;slow = fast = head;do {if ((fast = fast->next) != NULL) {fast = fast->next;slow = slow->next;}} while (fast);if (NULL == slow->next)return;//只有0或1个元素R.next = slow->next;slow->next = NULL;//一分为二mergeSortList(head);//使左半有序mergeSortList(&R);//使右半有序slow = head->next;fast = R.next;//两边准备进行归并}pre = head;//尾插法（是slow的前驱）do {if (fast->val < slow->val) {//右边比左边小pre = pre->next = fast;//原pre->next==slow，所以不会丢链fast = fast->next;pre->next = slow;//还原pre是slow的前驱if (fast == NULL) break;//左边的pre本来就接着slow，无需处理}else {//左边小pre = slow;slow = slow->next;if (slow == NULL) {pre->next = fast;//剩余的右边接到左边break;}}} while (true);}struct ListNode* sortList(struct ListNode* head) {struct ListNode Head; Head.next = head;//真正头结点，不参与排序mergeSortList(&Head);return Head.next;}
c++答案
/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:ListNode * merge(ListNode* left, ListNode* right){ListNode* newhead = NULL, *pre=NULL;while (left && right){if (left->val < right->val){if (!newhead){newhead = pre = left;left = left->next;}else{pre->next = left;pre = pre->next;left = left->next;}}else{if (!newhead){newhead = pre = right;right = right->next;}else{pre->next = right;pre = pre->next;right = right->next;}}}while (left){pre->next = left;left = left->next;pre = pre->next;}while (right){pre->next = right;right = right->next;pre = pre->next;}pre->next = NULL;return newhead;}ListNode* sortList(ListNode* head) {if (head == NULL || head->next == NULL)return head;else{ListNode* slow = head, *fast = head->next;while (fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}ListNode* temp = slow->next;slow->next = NULL;ListNode* l = sortList(head);ListNode* r = sortList(temp);return merge(l, r);}}};
java答案
/*** Definition for singly-linked list.* public class ListNode {*int val;*ListNode next;*ListNode(int x) { val = x; }* }*/class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;ListNode fast = head;ListNode slow = head;// 快慢指针寻找链表的中间节点while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}// 把链表分为两段ListNode l1 = head;ListNode l2 = slow.next;slow.next = null;// Merge Sortl1 = sortList(l1);l2 = sortList(l2);return merge(l1, l2);}// 归并两个已经排好序的链表private ListNode merge(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;ListNode dummy = new ListNode(-1);ListNode cur = dummy;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}if (l1 != null) cur.next = l1;else cur.next = l2;return dummy.next;}}
JavaScript答案
/*** Definition for singly-linked list.* function ListNode(val) {*this.val = val;*this.next = null;* }*//*** @param {ListNode} head* @return {ListNode}*/var merge = function(l1,l2) {var l = new ListNode();var p = l;while(l1 && l2) {if(l1.val < l2.val) {p.next = l1;l1 = l1.next} else {p.next = l2;l2 = l2.next}p = p.next}if(l1) {p.next = l1;}if(l2) {p.next = l2;}return l.next;}var sortList = function(head) {if(head === null || head.next === null) {return head;}var slow = head;var fast = head;var prev = null;while(fast && fast.next) {prev = slowfast = fast.next.next;slow = slow.next}prev.next = null;return merge(sortList(head), sortList(slow));};
c#答案
/*** Definition for singly-linked list.* public class ListNode {*public int val;*public ListNode next;*public ListNode(int x) { val = x; }* }*/public class Solution {public ListNode SortList(ListNode head) {if(head == null) return head; ListNode now = head;List<int> list = new List<int>();while(now != null){list.Add(now.val);now = now.next;}list.Sort();int length = list.Count;ListNode result = new ListNode(list[0]);now = result;for(int i=1;i<length;i++){now.next = new ListNode(list[i]);now = now.next;}return result;}}
python2.x答案
# Definition for singly-linked list.# class ListNode(object):#def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""node = headres=[]while node:res.append(node.val)node = node.nextres.sort()if not res:return Nonenewhead = ListNode(res[0])cur_Node = newheadfor i,v in enumerate(res):if i == 0:continueobj = ListNode(v)cur_Node.next=objcur_Node=objreturn newhead
python3.x答案
# Definition for singly-linked list.# class ListNode:#def __init__(self, x):# self.val = x# self.next = Noneclass Solution:def sortList(self, head):""":type head: ListNode:rtype: ListNode"""if not head: return None res = []while head:res.append(head)head = head.nextres.sort(key = lambda ele: ele.val)temp = res[0]for i in range(1,len(res)):temp.next = res[i]temp = res[i]res[-1].next = None return res[0]
go答案
/*** Definition for singly-linked list.* type ListNode struct {*Val int*Next *ListNode* }*/func sortList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}middle := split(head)return merge(sortList(head), sortList(middle))}// 双指针切分listfunc split(head *ListNode) *ListNode {slow, fast := head, headvar tail *ListNodefor fast != nil && fast.Next != nil {tail = slowslow = slow.Nextfast = fast.Next.Next}tail.Next = nilreturn slow}func merge(left ,right *ListNode) *ListNode {var head, cur, pre *ListNodefor left != nil && right != nil {if left.Val < right.Val {cur = leftleft = left.Next} else {cur = rightright = right.Next}// 生成headif head == nil {head = cur} else {pre.Next = cur}pre = cur}if left == nil {pre.Next = right} else {pre.Next = left}return head}
4. 算法面试自由的神器
更多算法题目精解 请微信扫一扫小程序 “算法面试宝典”， 实现算法面试自由的神器
如果觉得《字节跳动校招秋招算法面试真题解题报告--leetcode148 排序链表 内含7种语言答案》对你有帮助，请点赞、收藏，并留下你的观点哦！
