150 - 148 排序链表

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

解答

归并排序

https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

先用快慢指针，把链表从中间拆开，递归排序。排序方法是新建链表。

Picture2.png

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left, right = Solution.sortList(
            self, head), Solution.sortList(self, mid)
        point = ans = ListNode(0)
        while left and right:
            if left.val < right.val:
                point.next, left = left, left.next
            else:
                point.next, right = right, right.next
            point = point.next
        point.next = left if left else right
        return ans.next

Runtime: 224 ms, faster than 73.64% of Python3 online submissions for Sort List.

Memory Usage: 19.6 MB, less than 100.00% of Python3 online submissions for Sort List.

var sortList = function(head) {
  if (!head || !head.next) {
    return head
  }
  let fast = head.next
  slow = head
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
  }
  let mid = slow.next
  slow.next = null
  let left = sortList(head)
  right = sortList(mid)
  ans = new ListNode(0)
  p = ans
  while (left && right) {
    if (left.val < right.val) {
      p.next = left
      left = left.next
    } else {
      p.next = right
      right = right.next
    }
    p = p.next
  }
  if (left) {
    p.next = left
  } else {
    p.next = right
  }
  return ans.next
};

Runtime: 104 ms, faster than 40.33% of JavaScript online submissions for Sort List.

Memory Usage: 40.3 MB, less than 100.00% of JavaScript online submissions for Sort List.

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    fast := head.Next
    slow := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    mid := slow.Next
    slow.Next = nil
    left := sortList(head)
    right := sortList(mid)
    ans := &ListNode{}
    p := ans
    for left != nil && right != nil {
        if left.Val < right.Val {
            p.Next = left
            left = left.Next
        } else {
            p.Next = right
            right = right.Next
        }
        p = p.Next
    }
    if left != nil {
        p.Next = left
    } else {
        p.Next = right
    }
    return ans.Next
}

Runtime: 12 ms, faster than 83.94% of Go online submissions for Sort List.

Memory Usage: 5 MB, less than 100.00% of Go online submissions for Sort List.