LeetCode148 排序链表

• 题目
• 解题
• • 解题一：自顶向下归并排序
  • 解题二：自底向上归并排序

题目

解题

题目对时间复杂度有要求，采用归并排序。建议先做一下 LeetCode21 合并两个有序链表。

解题一：自顶向下归并排序

和官方解答的实现有些不同，首先判断是否满足两个终止条件，再去寻找左半截链表的结尾，快慢指针的方法在也有使用 LeetCode234 &《程序员面试金典》面试题 02.06. 回文链表，通过左半截链表的结尾找到寻找右半截链表的开头，接着一定要将 两段链表从中截断 （firstHalfEnd.next = null;）再分别排序后进行合并。

// javascript
var sortList = function(head) {
    if (head === null) return null;               // 链表为空，返回 null
    if (head.next === null) return head;          // 链表仅有一个节点，返回 head
    let firstHalfEnd = searchfirstHalfEnd(head);  // 寻找左半截链表的结尾
    let secondHalfStart = firstHalfEnd.next;      // 寻找右半截链表的开头
    firstHalfEnd.next = null;                     // 将两段链表截断
    let listLeft = sortList(head);                // 对左半截链表进行排序
    let listRight = sortList(secondHalfStart);    // 对右半截链表进行排序
    return mergeTwoLists(listLeft, listRight);    // 合并两个有序链表
};

// 寻找左半截链表的结尾
var searchfirstHalfEnd = function(head) {
    if (head === null) return null; // 此题可以省去，因为调用前判断过head不为null
    let fast = slow = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

// 合并两个有序链表
var mergeTwoLists = function(l1, l2) {
    const dummyHead = new ListNode();
    let cur = dummyHead;
    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;
    }
    cur.next = (l1 === null) ? l2 : l1;
    return dummyHead.next;
};

根据主定理：

T ( n ) = 2 ∗ T ( n / 2 ) + n T(n) = 2*T(n/2) + n T(n)=2∗T(n/2)+n, a = 2, b = 2, d = 1, 2 = 2 ^ 1, 时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)

解题二：自底向上归并排序

空间复杂度更优，思想是：先将长度为1的链表两两合并，再将长度为2的有序链表两两合并…但是对于链表而言，写起来比较繁琐，容易出错。

// javascript
var sortList = function(head) {
    if (head === null) return head;
    let length = getLength(head);
    const dummyHead = new ListNode(0, head);
    for (let subLength = 1; subLength < length; subLength <<= 1) {
        let prev = dummyHead, curr = dummyHead.next;
        while (curr !== null) {
            const head1 = curr;                                     // 找到 head1
            const head2 = moveAheadAndSplit(head1, subLength - 1);  // 找到 head2
            const next = moveAheadAndSplit(head2, subLength - 1);   // 找到下一段要处理的链表
            const merged = mergeTwoLists(head1, head2);             // 合并两个有序链表
            prev.next = merged;                                     // 将前面已被操作过的链表连上新合并好的链表
            while (prev.next !== null) {                            // 找到新的已被操作过的链表的最后一个非空节点
                prev = prev.next;
            }
            curr = next;                                            // curr 指向下一次需要操作的链表开头
        }
    }
    return dummyHead.next;
};

const getLength = (head) => {
    let length = 0;
    while (head !== null) {
        length++;
        head = head.next;
    }
    return length;
};

const moveAheadAndSplit = (head, count) => {
    // 找到 head 链表最后一个非空节点（有可能为空)
    while (count > 0 && head !== null) {
        head = head.next;
        count--;
    }
    let nextHead = null;
    if (head !== null) {           // 如果非空
        nextHead = head.next;      // 记录下一段链表开头
        head.next = null;          // 将该链表与下一段链表截断
    }
    return nextHead;               // 返回下一段链表开头
};

const mergeTwoLists = (l1, l2) => {
    const dummyHead = new ListNode();
    let cur = dummyHead;
    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;
    }
    cur.next = (l1 === null) ? l2 : l1;
    return dummyHead.next;
};