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 = []
输出：[]

提示： 

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

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

解题方法：类似数组的归并排序法。解题过程如下

1. 找到链表的中间节点。

2. 拆分链表，将原链表一分为二。

3. 分别对区间[head, mid]和[mid->next,tail]组成两个链表内部各自排序。

4. 将两个有序空间合并。

C++代码

#include <iostream>
#include <memory> //std::shared_ptr
/*** 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) {}*     1->2->3->4->5*.    1->2->3->4->5->6* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next) { //空链表或者链表仅包含一个节点return head;}//1. 找到链表的中间节点ListNode* p_mid = get_mid_node(head);if (!p_mid) {return nullptr;}//2. 拆分链表，将原链表一分为二ListNode *head1 = p_mid->next;//获取后半部分的head节点p_mid->next = nullptr;//拆分前半部分//3. 分别对区间[head, mid], [mid->next,tail]排序head = sortList(head);//对左半部分排序head1 = sortList(head1);//对右半部分排序//4. 将两个有序空间合并return merge(head, head1);//返回合并后的链表}// 快慢指针获取链表的中间节点ListNode* get_mid_node(ListNode* head) {if (!head || !head->next) {return head;}ListNode* p1 = head;//一次走1步的慢指针ListNode* p2 = head;//一次走2步的快指针while (p2 && p2->next && p2->next->next) {p1 = p1->next;p2 = p2->next->next;}return p1;}// 合并两个有序的链表ListNode* merge(ListNode* head1, ListNode* head2) {if (!head1) {return head2;}if (!head2) {return head1;}std::shared_ptr<ListNode> dummy_node(new ListNode(0));ListNode* p = dummy_node.get();//用哨兵节点可以避免对新链表头节点单独判断ListNode* p1 = head1;ListNode* p2 = head2;while (p1 && p2) {if (p1->val <= p2->val) {p->next = p1;p1 = p1->next;} else {p->next = p2;p2 = p2->next;}p = p->next;}if (p1) { //head1更长p->next = p1;}if (p2) { //head2更长p->next = p2;}return dummy_node->next;}
};