AlgoViz Lab交互式算法学习
Algorithms first

排序链表 · 交互式算法学习

在 O(n log n) 时间内排序链表。

#148 · 分治

排序链表

Sort List

测试用例head = [4,2,1,3]
链表3 个关键状态
步骤 1快慢指针切成 [4,2] 与 [1,3]。split
4next
→
2next
→
1next
→
3next
null
推荐

链表归并排序

时间 O(n log n)空间 O(log n)

快慢指针切半，递归排序两半，再线性合并。

1function sortList(head) {2  if (!head || !head.next) return head;3  let slow = head,4    fast = head.next;5  while (fast && fast.next) {6    slow = slow.next;7    fast = fast.next.next8  }9  const right = slow.next;10  slow.next = null;11  return merge(sortList(head), sortList(right));12 13  function merge(a, b) {14    const d = {15      next: null16    };17    let p = d;18    while (a && b) {19      if (a.val < b.val) {20        p.next = a;21        a = a.next22      } else {23        p.next = b;24        b = b.next25      }26      p = p.next27    }28    p.next = a || b;29    return d.next30  }31}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode sortList(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16        ListNode slow = head, fast = head.next;17        while (fast != null && fast.next != null) {18            slow = slow.next;19            fast = fast.next.next;20        }21        ListNode l1 = head, l2 = slow.next;22        slow.next = null;23        l1 = sortList(l1);24        l2 = sortList(l2);25        ListNode dummy = new ListNode();26        ListNode tail = dummy;27        while (l1 != null && l2 != null) {28            if (l1.val <= l2.val) {29                tail.next = l1;30                l1 = l1.next;31            } else {32                tail.next = l2;33                l2 = l2.next;34            }35            tail = tail.next;36        }37        tail.next = l1 != null ? l1 : l2;38        return dummy.next;39    }40}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

排序链表 · 解法对比

AlgoViz Lab

在 O(n log n) 时间内排序链表。

测试用例
head = [4,2,1,3]
题目分类
分治
解法对比
2
方案 1

收集数组排序再写回

把值放数组排序，再依次写回节点。

时间
O(n log n)
空间
O(n)
方案 2

链表归并排序

快慢指针切半，递归排序两半，再线性合并。

时间
O(n log n)
空间
O(log n)