面试经典150题 P148 排序链表

---

时间轴

2025-12-01

init

---

题目：

P148 排序链表

https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150

归并排序：

struct ListNode {
	int val;
	ListNode *next;
	ListNode()
		: val(0)
		, next(nullptr)
	{
	}
	ListNode(int x)
		: val(x)
		, next(nullptr)
	{
	}
	ListNode(int x, ListNode *next)
		: val(x)
		, next(next)
	{
	}
};

class Solution {
    private:
	ListNode *mergeSort(ListNode *head)
	{
		if (head == nullptr || head->next == nullptr) {
			return head;
		}

		// 归并排序
		ListNode *low, *fast;
		low = head;
		fast = head->next;
		// find middle
		while (fast != nullptr && fast->next != nullptr) {
			low = low->next;
			fast = fast->next->next;
		}
		ListNode *h2_head = low->next;
		low->next = nullptr;
		//now low is middle
		ListNode *h1 = mergeSort(head); // head ... low
		ListNode *h2 = mergeSort(h2_head); // low .. tail

		// merge
		ListNode dummy;
		ListNode *tail = &dummy, *tmp;
		while (h1 || h2) {
			if ((h1 && h2 && h1->val < h2->val) || (h1 && !h2)) {
				tail->next = h1;
				tail = h1;
				h1 = h1->next;
				tail->next = nullptr;

			} else if ((h1 && h2 && h1->val >= h2->val) || (!h1 && h2)) {
				tail->next = h2;
				tail = h2;
				h2 = h2->next;
				tail->next = nullptr;
			}
		}

		return dummy.next;
	}

    public:
	ListNode *sortList(ListNode *head)
	{
		return mergeSort(head);
	}
};