Interview Classic 150 Questions P148 Sort List

---

Timeline

Timeline

2025-12-01

init

Divide and Conquer, Merge Sort

---

Problem:

P148 Sort List

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

Merge Sort:

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;
		}

		// Merge Sort
		ListNode *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);
	}
};

Merge Sort: Divide first, then merge

leetcode hot 100 rewrite

#include <vector>
#include <algorithm>
#include <utility>
using std::vector;
using std::pair;

class Solution {
    public:
        ListNode *sortList(ListNode *head)
        {
                if (head == nullptr)
                        return nullptr;
                vector<pair<int, ListNode *> > arr;
                int i, n;
                ListNode *p = head;

                while (p) {
                        arr.push_back({ p->val, p });
                        p = p->next;
                }

                std::sort(arr.begin(), arr.end(),
                          [](pair<int, ListNode *> &a, pair<int, ListNode *> &b) {
                                  return a.first < b.first;
                          });

                n = arr.size();
                for (i = 0; i < n - 1; i++) {
                        arr[i].second->next = arr[i + 1].second;
                }
                arr[n - 1].second->next = nullptr;
                return arr[0].second;
        }
};