原题

解法

思路：
1、快慢指针找到中间节点
2、以中间节点断链，不断分治
3、合并两个有序链表

  1. // way2：归并排序递归版
  2. function sortList(head){
  3.     if(head==null||head.next==null){
  4.         return head;
  5.     }
  6.     let 
  7.         slow = head,
  8.         preSlow = head,// 用于将两个链表隔断
  9.         fast = head;
  10.     // 快慢指针 找划分点
  11.     while(fast!=null&&fast.next!=null){
  12.         preSlow = slow;
  13.         slow = slow.next;
  14.         fast = fast.next.next;
  15.     }
  16.     preSlow.next = null;
  17.     # 以上全是分治阶段
  18.     return mergeList(sortList(head),sortList(slow));
  19.       # mergelist：回溯阶段做合并链表的事，并把合并后的链表返回，这样在回溯的时候做到了链表的串联
  21.     function mergeList(list1,list2){
  22.         // 一个辅助节点
  23.         let 
  24.             dummyHead = new ListNode(0),
  25.             cur = dummyHead;
  26.         while (list1!=null && list2!=null) {
  27.             if (list1.val < list2.val) {
  28.                 cur.next = list1;
  29.                 list1 = list1.next;
  30.             }
  31.             else {
  32.                 cur.next = list2;
  33.                 list2 = list2.next;
  34.             }
  35.             cur = cur.next;
  36.         }
  37.         cur.next = list1 || list2;
  38.         return dummyHead.next;
  39.     }
  40. }

当然也有绕开链表的路子：遍历链表，把数全部放入数组，然后对数组进行快排,再遍历数组 生成链表

function sortList(head){
    let arr = [];
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    // 从大到小排 然后使用头插法
    let arr_sorted = arr.sort((a,b)=>b-a)

    let dummy = new ListNode();
    arr_sorted.forEach(item=>{
        let newnode = new ListNode(item);
        newnode.next = dummy.next;
        dummy.next = newnode;
    })
    return dummy.next;
}

不过这里主要还是探讨归并排序的解法。
归并排序至少用到了三个知识点：
1、定位链表的中间结点
2、合并两个有序链表
3、链表的递归

知识点1：链表中间结点

var middleNode = function(head) {
    let fast = slow = head;
    while(fast&&fast.next){
        fast = fast.next.next
        slow = slow.next
    }
    return slow;
};

知识点2：合并两个有序链表

迭代版


function mergeTwoLists(l1,l2){
    let dummy = new ListNode();// 头结点
    let curr = dummy;
    while(l1&&l2){
        if(l1.val<l2.val){
            curr.next  = l1;
            l1 = l1.next
        }else{
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    //curr = l1?l1:l2;
    curr.next = l1?l1:l2
    return dummy.next;
}

递归版

var mergeTwoLists = function(l1, l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    if(l1.val<l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next  = mergeTwoLists(l1,l2.next);
        return l2;
    }
};

知识点3：链表的递归

可以通过以下题目练习链表的递归（最好是用迭代写法解决过下面的题，然后考虑使用递归重构）

  • 链表遍历（正序输出、反序输出）
  • 反转链表
  • 回文链表
  • 两个有序链表合并