leetcode148 Sort List
题目内容
算法分析<喎?http://www.weiyer.com/Search.asp?KeyWord=/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPs/gttTT2sqxvOS4tNTTtsjOqk8obmxvZ24ptcTFxdDyy+O3qKOs09C/7MvZxcXQ8rrNuemyosXF0PKho9XiwO+yydPDtcTKx7npsqLFxdDyoaPLvMK3tPPWwsjnz8KjujxiciAvPg0KuemyosXF0PK1xLTz1sLLvM/rvs3Kx6OsvavBtLHtt9azycG9ts6jrMi7uvPNqLn9td256buut9ajrLbUwbSx7bXEx7Cw67K/t9a6zbrzsOuyv7fWvfjQ0MXF0PK689TZvfjQ0LnpsqLFxdDyo6zX7rrzttTFxbrD0PK1xMG0se29+NDQus+yoqGjxNG149au0rvKx72rwbSx7buut9azycG9ts6jrLLJ08O1xMrHZmFzdHNsb3cuwb249ta41eujrNK7uPbWuNXr19/BvbK9o6zB7dK7uPbWuNXr19/Su7K9oaPX38G9sr21xNa41eu1vbTvveHOsrXEzrvWw6Os19/Su7K9tcTWuNXruNW6w7W9tO/W0LzktcTOu9bDo6zU8rfWs8nBy8G9ts6jrLrzvfjQ0G1lcmdlLjwvcD4NCjxwPrT6wuvKtc/Wo6hqYXZhU2NyaXB0o6k8L3A+DQo8cHJlIGNsYXNzPQ=="brush:sql;">
/**
Definition for singly-linked list.
function ListNode(val) {
this.val = val;
this.next = null;
}
*/
/**
@param {ListNode} head
@return {ListNode}
*/
var sortList = function(head) {
if(head===null||head.next===null){
return head;
}
return mergeSort(head);
};
function mergeSort(head){
if(head.next===null){
return head;
}
var pHead,qHead,pre;
pHead=head;
qHead=head;
pre=null;
while(qHead!==null&&qHead.next!==null){
qHead=qHead.next.next;
pre=pHead;
pHead=pHead.next;
}
pre.next=null;
var l,r;
l=mergeSort(head);
r=mergeSort(pHead);
return merge(l,r);
}
function merge(l,r){
var pRes=new ListNode(0);
var temp=pRes;
while(l!==null&&r!==null)
{
if(l.val<=r.val)
{
temp.next=l;
temp=temp.next;
l=l.next;
}
else
{
temp.next=r;
temp=temp.next;
r=r.next;
}
}
if(l!==null)
temp.next=l;
if(r!==null)
temp.next=r;
temp=pRes.next;
pRes=null;
return temp;
}
结果展示
