148. 排序链表

原题链接：LeetCode 148. 排序链表

题目描述

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3] 输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]

示例 3：

输入：head = [] 输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

难度： Medium

题解代码

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 || !head.next) return head

    const mid = middleNode(head)
    
    const rightHead = mid.next
    mid.next = null

    const left = sortList(head)
    const right = sortList(rightHead)

    return mergeTwoLists(left, right)
};

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

// 21题
var mergeTwoLists = function(l1, l2) {
    const preHead = new ListNode(-1)
    let p = preHead
    while (l1 && l2) {
      if (l1.val > l2.val) {
        p.next = l2
        l2 = l2.next
      } else {
        p.next = l1
        l1 = l1.next
      }
      p = p.next
    }
    p.next = l1 || l2
    return preHead.next
  };

  var sortList = function(head) {
    if (!head || !head.next) return head
    // 找到中间节点 切断链表
    let slow = head
    let fast = head.next
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    const rightHead = slow.next
    slow.next = null

    let left = sortList(head)
    let right = sortList(rightHead)

    // 合并两个链表
    const preHead = new ListNode(-1)
    let p = preHead
    while (left && right) {
      if (left.val > right.val) {
        p.next = right
        right = right.next
      } else {
        p.next = left
        left = left.next
      }
      p = p.next
    }
    p.next = left || right
    return preHead.next
};

148. 排序链表 #

题目描述 #

题解代码 #

148. 排序链表

题目描述

题解代码