力扣148:排序链表

题目

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

思路

当我们第一眼看见这道题时心中其实是有思路的，我们不想这是个链表就当它是一个整型数组。那么自然而然就会想到各种各样的排序方法，第一眼看上去大部分想到的可能是把这个一分为变成两个子数组再对子数组进行排序。这个想法同样适用于链表只不过只分一次并不行我们需要将其分到彻底分不了也就是只剩一个节点或者干脆没有节点可分。在分完后就好做了啊两个节点还不好做升序排序吗？再往上就算变成了一个链表也是个有序链表，两个有序链表连接起来不也很好做吗。所以这道题的主要就是我们需要想到先将其分开再组合也就是使用分治的思想。
同时这一样也是一种排序方法也就是归并排序只不过归并排序不止可以通过分治来完成还可以使用迭代所以这道题同样也有另外一个方法我就不再说了。无论是分治还是迭代最后完成的都是归并排序，我们使用分治也就是自顶向下进行归并排序。

代码

/*** 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* sortList(ListNode* head) {// 归并排序// 运用分治的思想// 将链表进行划分直到为单个节点// 然后一个一个的连接起来return MergeSort(head, nullptr);}ListNode* MergeSort(ListNode* head, ListNode* tail) {// 直到只剩一个节点或者没有节点if (head == nullptr) {return head;}if (head->next == tail) {head->next = nullptr;return head;}// 寻找中点进行划分ListNode* cur = head;ListNode* prev = head;while (cur != tail && cur->next != tail) {cur = cur->next->next;prev = prev->next;}ListNode* mid = prev;return merge(MergeSort(head, mid), MergeSort(mid, tail));}ListNode* merge(ListNode* list1, ListNode* list2) {// 治也就是连接两个链表// 哨兵节点，方便返回ListNode* newnode = new ListNode(0);ListNode* node = newnode;ListNode* node1 = list1;ListNode* node2 = list2;// 连接节点直到两个链表有一个为空while (node1 != nullptr && node2 != nullptr) {if (node1->val < node2->val) {node->next = node1;node1 = node1->next;} else {node->next = node2;node2 = node2->next;}node = node->next;}// 由于先划分到最底层一个一个节点// 再从一个一个节点组合成链表的// 所以两个链表最多只会多一个节点if (node1 != nullptr) {node->next = node1;node1 = node1->next;node = node->next;}if (node2 != nullptr) {node->next = node2;node2 = node2->next;node = node->next;}return newnode->next;}
};