排序链表
1.题目形容
<p>在 O(n log n) 工夫复杂度和常数级空间复杂度下，对链表进行排序。</p><br/><p>示例 1:</p><br/><pre>输出: 4->2->1->3<br/>输入: 1->2->3->4<br/></pre><br/><p>示例 2:</p><br/><pre>输出: -1->5->3->4->0<br/>输入: -1->0->3->4->5</pre><br/>
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}