LeetCode148 排序链表

发表于 | 分类于 |
字数统计: 366 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/sort-list/

题意

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

解法

链表的排序
经常使用的是归并排序，链表的结构可以得到充分的利用
主要分三步，第一步是找出中间节点（快慢指针）
第二步将两个递归处理链表的前半部分和后半部分
第三步将两个处理后的链表进行归并
像是一系列链表题目的组合，是一道很能考察链表功底的题

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * 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 {
public:
    ListNode* findMid(ListNode* head) { // 找出中间节点
        ListNode* slow = head, *fast = head -> next;
        while(fast != nullptr && fast -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        return slow;
    }

    ListNode* merge(ListNode* pa, ListNode* pb) { // 进行归并
        if (!(pa && pb)) return pa ? pa : pb;
        ListNode* dummy = new ListNode(), *head = dummy;
        while(pa != nullptr && pb != nullptr) {
            if (pa -> val < pb -> val) {
                head -> next = pa;
                pa = pa -> next;
            }
            else {
                head -> next = pb;
                pb = pb -> next;
            }
            head = head -> next;
        }
        if (pa) head -> next = pa;
        if (pb) head -> next = pb;
        return dummy -> next;
    }

    ListNode* sortList(ListNode* head) { // 归并排序
        if (head == nullptr || head -> next == nullptr) return head;
        ListNode* mid = findMid(head);
        ListNode* pb = sortList(mid -> next);
        mid -> next = nullptr;
        ListNode* pa = sortList(head);
        return merge(pa, pb);
    }
};