leetcode148SortList

leetcode148 Sort List

题目内容

算法分析

相对于时间复杂度为O(nlogn)的排序算法，有快速排序和归并排序。这里采用的是归并排序。思路大致如下：
归并排序的大致思想就是，将链表分成两段，然后通过递归划分，对链表的前半部分和后半部分进行排序后再进行归并排序，最后对排好序的链表进行合并。难点之一是将链表划分成两段，采用的是fastslow.两个指针，一个指针走两步，另一个指针走一步。走两步的指针到达结尾的位置，走一步的指针刚好到达中间的位置，则分成了两段，后进行merge.

代码实现（javaScript）

  /**
  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; 
    }