LeetCode-148. Sort List

发表于 分类于

问题描述

Given the head of a linked list, return the list after sorting it in ascending order.

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

解答

方法一：归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 * @Description: 148. Sort List
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @description: 使用归并排序的思想
 * @param {ListNode} head
 * @return {ListNode}
 */
const sortList2 = function (head) {
  if (head === null || head.next === null) {
    return head
  }
  let pre = null
  let slow = head
  let fast = head
  while (fast !== null && fast.next !== null) {
    pre = slow
    slow = slow.next
    fast = fast.next.next
  }
  pre.next = null
  return merge(sortList(head), sortList(slow))
}

function merge(head1, head2) {
  if (head1 === null) {
    return head2
  }
  if (head2 === null) {
    return head1
  }
  let dummy = new ListNode()
  let pre = dummy
  while (head1 !== null && head2 !== null) {
    if (head1.val > head2.val) {
      pre.next = head2
      head2 = head2.next
    } else {
      pre.next = head1
      head1 = head1.next
    }
    pre = pre.next
  }
  pre.next = (head1 === null) ? head2 : head1
  return dummy.next
}
方法二：转换成数组后排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
 * @Description: 148. Sort List
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @description: 先转换成数组，再进行排序，再转回链表
 * @param {ListNode} head
 * @return {ListNode}
 */
const sortList = function (head) {
  let arr = []
  let p = head
  while (p !== null) {
    arr.push(p.val)
    p = p.next
  }
  arr.sort(function (a, b) {
    return a - b
  })
  let dummy = new ListNode(0)
  p = dummy
  while (arr.length) {
    p.next = new ListNode(arr.shift())
    p = p.next
  }
  return dummy.next
}