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 head ListNode* 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 Sort l1 = 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 = slow fast = 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 = head res=[] while node: res.append(node.val) node = node.next res.sort() if not res: return None newhead = ListNode(res[0]) cur_Node = newhead for i,v in enumerate(res): if i == 0: continue obj = ListNode(v) cur_Node.next=obj cur_Node=obj return 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.next res.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, head var tail *ListNode for fast != nil && fast.Next != nil { tail = slow slow = slow.Next fast = fast.Next.Next } tail.Next = nil return slow}func merge(left ,right *ListNode) *ListNode { var head, cur, pre *ListNode for left != nil && right != nil { if left.Val < right.Val { cur = left left = left.Next } else { cur = right right = right.Next } // 生成head if head == nil { head = cur } else { pre.Next = cur } pre = cur } if left == nil { pre.Next = right } else { pre.Next = left } return head}