LeetCode-148.排序链表

发表于 分类于

题目描述

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

示例

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

题解

方法1

借助数组sort方法排序后重新生成新的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func sortList(_ head: ListNode?) -> ListNode? {
  var list: [Int] = []
  var cur = head
  while cur !== nil {
    list.append(cur!.val)
    cur = cur?.next
  }
  list.sort(by: <)
  let res: ListNode? = ListNode(Int.min)
  cur = res
  list.forEach { value in
    cur?.next = ListNode(value)
    cur = cur?.next
  }
  return res?.next
}

方法2

归并排序

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
func sortList2(_ head: ListNode?) -> ListNode? {
  if head === nil || head?.next === nil {
    return head
  }
  var left = head
  var mid = head?.next
  var right = head?.next?.next
  // 将链表一分为二，从left和mid之间断开
  while right !== nil && right?.next !== nil {
    left = left?.next
    mid = mid?.next
    right = right?.next?.next
  }
  left?.next = nil
  return mergeTwoLists(sortList2(head), sortList2(mid))
}
// 合并两个链表
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
  if list1 == nil {
    return list2
  }
  if list2 == nil {
    return list1
  }
  let head = ListNode(0)
  var cur = head
  var l1 = list1
  var l2 = list2
  while l1 !== nil && l2 !== nil {
    if let val1 = l1?.val, let val2 = l2?.val {
      if val1 <= val2 {
        cur.next = l1
        l1 = l1?.next
      } else {
        cur.next = l2
        l2 = l2?.next
      }
    }
    cur = cur.next!
  }
  if l1 !== nil {
    cur.next = l1
  } else if l2 !== nil {
    cur.next = l2
  }
  return head.next
}