148. 排序链表

题目描述

输入单链表的头节点 head。把链表按节点值从小到大排序，返回排序后的头节点。

链表用数组表示，例如 [1,2,3]。空链表返回空。

示例 1

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

解释：升序排列后为 [1,2,3,4]。

示例 2

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

解释：升序排列后为 [-1,0,3,4,5]。

示例 3

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

解释：空链表没有节点，返回空。

数据范围

节点数在 [0, 5 * 10^4] 之间。
-10^5 <= Node.val <= 10^5

进阶：能否在 O(n log n) 时间内、只用常数级额外空间完成排序？

解题思路：自顶向下归并排序

快慢指针分成两段，递归排序后用双指针合并。

为什么正确

每次合并的两条输入链都已经有序，合并前缀始终有序。

复杂度分析

时间 O(n log n)，递归栈 O(log n)，合并额外空间 O(1)。

易错点

拆分时必须断开 slow.next，否则递归区间不会缩小。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def sortList(self, head):
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        slow.next = None
        a, b = self.sortList(head), self.sortList(right)
        dummy = ListNode(0)
        tail = dummy
        while a and b:
            if a.val <= b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        slow.next = null;
        ListNode a = sortList(head), b = sortList(right);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) {
                tail.next = a; a = a.next;
            } else {
                tail.next = b; b = b.next;
            }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* right = slow->next;
        slow->next = nullptr;
        ListNode *a = sortList(head), *b = sortList(right);
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a; a = a->next;
            } else {
                tail->next = b; b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }
};

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	right := slow.Next
	slow.Next = nil
	a, b := sortList(head), sortList(right)
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

var sortList = function(head) {
    if (!head || !head.next)
        return head;
    let slow = head, fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    const right = slow.next;
    slow.next = null;
    let a = sortList(head), b = sortList(right);
    const dummy = new ListNode(0);
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) {
            tail.next = a; a = a.next;
        } else {
            tail.next = b; b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
};

function sortList(head: ListNode | null): ListNode | null {
    if (!head || !head.next)
        return head;
    let slow: ListNode = head, fast: ListNode | null = head.next;
    while (fast && fast.next) {
        slow = slow.next!;
        fast = fast.next.next;
    }
    const right = slow.next;
    slow.next = null;
    let a = sortList(head), b = sortList(right);
    const dummy = new ListNode(0);
    let tail: ListNode = dummy;
    while (a && b) {
        if (a.val <= b.val) {
            tail.next = a; a = a.next;
        } else {
            tail.next = b; b = b.next;
        }
        tail = tail.next!;
    }
    tail.next = a || b;
    return dummy.next;
};

载入编辑器，自己跑一遍 →

其他解法

两种方法时间都是 O(n log n)；自顶向下靠递归找中点，好写但占 O(log n) 栈空间；自底向上用循环按步长合并，空间 O(1)。

解法 2：自底向上归并排序时间 O(n log n)，空间 O(1)

先求链表长度 n。子链长度 step 从 1 开始，每轮翻倍。每轮从头把链表切成长度为 step 的两段，合并后接到已处理部分的尾部，再处理后面的两段。step 不小于 n 时排序完成。

不用递归，额外空间降到 O(1)，满足进阶要求。需要写切断子链和接回尾部的逻辑，比自顶向下更容易出错。

class Solution:
    def sortList(self, head):
        def cut(h, k):
            while h and k > 1:
                h = h.next
                k -= 1
            if not h:
                return None
            rest = h.next
            h.next = None
            return rest

        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        dummy = ListNode(0, head)
        step = 1
        while step < n:
            prev, cur = dummy, dummy.next
            while cur:
                a = cur
                b = cut(a, step)
                cur = cut(b, step)
                tail = prev
                while a and b:
                    if a.val <= b.val:
                        tail.next, a = a, a.next
                    else:
                        tail.next, b = b, b.next
                    tail = tail.next
                tail.next = a or b
                while tail.next:
                    tail = tail.next
                prev = tail
            step *= 2
        return dummy.next

class Solution {
    private ListNode cut(ListNode head, int k) {
        while (head != null && --k > 0) head = head.next;
        if (head == null) return null;
        ListNode rest = head.next;
        head.next = null;
        return rest;
    }

    public ListNode sortList(ListNode head) {
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) n++;
        ListNode dummy = new ListNode(0, head);
        for (int step = 1; step < n; step *= 2) {
            ListNode prev = dummy, cur = dummy.next;
            while (cur != null) {
                ListNode a = cur;
                ListNode b = cut(a, step);
                cur = cut(b, step);
                ListNode tail = prev;
                while (a != null && b != null) {
                    if (a.val <= b.val) { tail.next = a; a = a.next; }
                    else { tail.next = b; b = b.next; }
                    tail = tail.next;
                }
                tail.next = a != null ? a : b;
                while (tail.next != null) tail = tail.next;
                prev = tail;
            }
        }
        return dummy.next;
    }
}

class Solution {
    ListNode* cut(ListNode* head, int k) {
        while (head && --k) head = head->next;
        if (!head) return nullptr;
        ListNode* rest = head->next;
        head->next = nullptr;
        return rest;
    }

public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) n++;
        ListNode dummy(0, head);
        for (int step = 1; step < n; step *= 2) {
            ListNode* prev = &dummy;
            ListNode* cur = dummy.next;
            while (cur) {
                ListNode* a = cur;
                ListNode* b = cut(a, step);
                cur = cut(b, step);
                ListNode* tail = prev;
                while (a && b) {
                    if (a->val <= b->val) { tail->next = a; a = a->next; }
                    else { tail->next = b; b = b->next; }
                    tail = tail->next;
                }
                tail->next = a ? a : b;
                while (tail->next) tail = tail->next;
                prev = tail;
            }
        }
        return dummy.next;
    }
};

func sortList(head *ListNode) *ListNode {
	cut := func(h *ListNode, k int) *ListNode {
		for h != nil && k > 1 {
			h = h.Next
			k--
		}
		if h == nil {
			return nil
		}
		rest := h.Next
		h.Next = nil
		return rest
	}
	n := 0
	for cur := head; cur != nil; cur = cur.Next {
		n++
	}
	dummy := &ListNode{Next: head}
	for step := 1; step < n; step *= 2 {
		prev, cur := dummy, dummy.Next
		for cur != nil {
			a := cur
			b := cut(a, step)
			cur = cut(b, step)
			tail := prev
			for a != nil && b != nil {
				if a.Val <= b.Val {
					tail.Next, a = a, a.Next
				} else {
					tail.Next, b = b, b.Next
				}
				tail = tail.Next
			}
			if a != nil {
				tail.Next = a
			} else {
				tail.Next = b
			}
			for tail.Next != nil {
				tail = tail.Next
			}
			prev = tail
		}
	}
	return dummy.Next
}

var sortList = function(head) {
    const cut = (h, k) => {
        while (h && --k) h = h.next;
        if (!h) return null;
        const rest = h.next;
        h.next = null;
        return rest;
    };
    let n = 0;
    for (let cur = head; cur; cur = cur.next) n++;
    const dummy = new ListNode(0, head);
    for (let step = 1; step < n; step *= 2) {
        let prev = dummy, cur = dummy.next;
        while (cur) {
            let a = cur;
            let b = cut(a, step);
            cur = cut(b, step);
            let tail = prev;
            while (a && b) {
                if (a.val <= b.val) { tail.next = a; a = a.next; }
                else { tail.next = b; b = b.next; }
                tail = tail.next;
            }
            tail.next = a || b;
            while (tail.next) tail = tail.next;
            prev = tail;
        }
    }
    return dummy.next;
};

function sortList(head: ListNode | null): ListNode | null {
    const cut = (h: ListNode | null, k: number): ListNode | null => {
        while (h && --k) h = h.next;
        if (!h) return null;
        const rest = h.next;
        h.next = null;
        return rest;
    };
    let n = 0;
    for (let cur = head; cur; cur = cur.next) n++;
    const dummy = new ListNode(0, head);
    for (let step = 1; step < n; step *= 2) {
        let prev: ListNode = dummy, cur: ListNode | null = dummy.next;
        while (cur) {
            let a: ListNode | null = cur;
            let b = cut(a, step);
            cur = cut(b, step);
            let tail: ListNode = prev;
            while (a && b) {
                if (a.val <= b.val) { tail.next = a; a = a.next; }
                else { tail.next = b; b = b.next; }
                tail = tail.next!;
            }
            tail.next = a || b;
            while (tail.next) tail = tail.next;
            prev = tail;
        }
    }
    return dummy.next;
}

链表专题的其他题目

查看链表全部题目 →