Voyz's Studio.

LeetCode算法笔记--排序链表

字数统计: 370阅读时长: 1 min
2021/01/15 Share

LeetCode算法笔记-Day62

148. Sort List

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

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

1
2
3
4
5
6
7
8
9
10
11
Example:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Input: head = []
Output: []

方法一:归并排序

1123455.png

Answer:

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
56
57
58
59
60
61
62
63
64
65
66
67
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/

let sortList = function(head) {
return mergeSortRec(head)
}

// 归并排序
// 若分裂后的两个链表长度不为 1,则继续分裂
// 直到分裂后的链表长度都为 1
// 然后合并小链表
let mergeSortRec = function (head) {
if(!head || !head.next) {
return head
}

// 获取中间节点
let middle = middleNode(head)
// 分裂成两个链表
let temp = middle.next
middle.next = null
let left = head, right = temp
// 继续分裂(递归分裂)
left = mergeSortRec(left)
right = mergeSortRec(right)
// 合并两个有序链表
return mergeTwoLists(left, right)
}

// 获取中间节点
// - 如果链表长度为奇数,则返回中间节点
// - 如果链表长度为偶数,则有两个中间节点,这里返回第一个
let middleNode = function(head) {
let fast = head, slow = head
while(fast && fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}

// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {
let preHead = new ListNode(-1);
let cur = preHead;
while(l1 && l2){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 || l2;
return preHead.next;
}
CATALOG
  1. 1. LeetCode算法笔记-Day62
    1. 1.1. 148. Sort List
    2. 1.2. 方法一:归并排序
      1. 1.2.1. Answer: