148. Sort List
Tags:
Medium
Skills:
Divide & conquer
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu sắp xếp một singly linked list theo thứ tự tăng dần. Vì không thể truy cập ngẫu nhiên các phần tử như mảng, các thuật toán sắp xếp như quicksort hoặc heapsort sẽ không hiệu quả. Thuật toán tối ưu nhất cho linked list là merge sort vì
Approach
slow và fast để tìm điểm giữa của linked list khi fast đến cuối, slow ở giữa. Cắt đôi danh sách tại vị trí nàySolution
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function sortList(head: ListNode | null): ListNode | null {
14 if (!head || !head.next) return head;
15 let slow = head, fast = head, prev = null
16 while (fast && fast.next) {
17 prev = slow;
18 slow = slow.next;
19 fast = fast.next.next;
20 }
21
22 prev.next = null
23 const l1 = sortList(head);
24 const l2 = sortList(slow)
25 return merge(l1, l2)
26};
27
28function merge(l1: ListNode | null, l2: ListNode | null): ListNode | null {
29 const dummy = new ListNode(0);
30 let tail = dummy;
31 while (l1 && l2) {
32 if (l1.val < l2.val) {
33 tail.next = l1;
34 l1 = l1.next
35 } else {
36 tail.next = l2;
37 l2 = l2.next
38 }
39 tail = tail.next
40 }
41 tail.next = l1 || l2;
42 return dummy.next;
43}