What is the most efficient way to sort a linked list in LeetCode 148?

Using merge sort directly on the linked list with careful pointer manipulation ensures O(n log n) time and minimal extra space.

Can I convert the linked list to an array and sort it?

While possible, this approach loses the pointer manipulation pattern and increases space complexity, which may be penalized in interviews.

How do fast and slow pointers help in Sort List?

They locate the middle node efficiently to split the list into halves for recursive merge sort, maintaining balanced recursion.

What are common mistakes when merging sorted linked lists?

Forgetting to update next pointers, losing track of head and tail, or creating cycles are frequent pitfalls that break the sorted list.

Does the solution work for very large lists?

Yes, the O(n log n) merge sort with pointer manipulation handles up to 50,000 nodes efficiently without extra arrays.

#148

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。示例 1：输入： head = [4,2,1,3] 输出： [1,2,3,4] 示例 2：输入： head = [-1,5,3,4,0] 输出： [-1,0,3,4,5] 示例 3：输入： head = [] 输出： …

链表双指针分治排序归并排序

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10⁴] 内
-10⁵ <= Node.val <= 10⁵

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

lightbulb

解题思路

方法一：归并排序

我们可以用归并排序的思想来解决。

首先，我们利用快慢指针找到链表的中点，将链表从中点处断开，形成两个独立的子链表 $\textit{l1}$ 和 $\textit{l2}$ 。

然后，我们递归地对 $\textit{l1}$ 和 $\textit{l2}$ 进行排序，最后将 $\textit{l1}$ 和 $\textit{l2}$ 合并为一个有序链表。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是链表的长度。

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        l1, l2 = head, slow.next
        slow.next = None
        l1, l2 = self.sortList(l1), self.sortList(l2)
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to the divide-and-conquer merge sort approach. Space complexity is O(log n) for recursion stack; no additional arrays are used, keeping pointer manipulation efficient.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer may hint at avoiding array conversion for true pointer manipulation.
question_mark
Expect discussion on fast and slow pointers for splitting the linked list.
question_mark
They often ask how to merge sublists without extra space to verify understanding of linked-list operations.

warning

常见陷阱

外企场景

error
Accidentally creating cycles when reconnecting nodes during merge.
error
Not handling empty lists or single-node lists as base cases, causing null pointer errors.
error
Failing to update head or tail pointers correctly, leading to lost nodes in the final sorted list.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sort a doubly linked list using similar divide-and-conquer strategies but with backward pointers.
arrow_right_alt
Sort a linked list where nodes contain extra data that must remain paired with values.
arrow_right_alt
Implement iterative bottom-up merge sort instead of recursive sorting to reduce stack usage.

help

常见问题

外企场景

继续练习

#143 重排链表 #142 环形链表 II #141 环形链表