LeetCode：148. 排序链表

简介

题目链接：https://leetcode.cn/problems/sort-list/description/

解决方式：链表 + 分治法（递归 + 双指针）

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

推荐看灵茶山艾府、Krahets大佬的讲解。

分治法

解题思路：分治分治，分而治之。本题大体上是用递归将大的链表分成两个小的链表，直到小的链表不能再分。之后，就利用双指针按从小到大的顺序合并两个小链表。

需要解决两个前置题目：

• 876. 链表的中间结点
• 21. 合并两个有序链表

classSolution{publicListNodesortList(ListNodehead){// 边界处理（递归终止条件）if(head==null||head.next==null){returnhead;}// 递归公式// 得到分开后，第二个链表的头节点ListNodehead2=middleNode(head);// 分治head=sortList(head);head2=sortList(head2);// 合并returnmergeList(head,head2);}// 双指针寻找中间节点，即第二个链表的头节点privateListNodemiddleNode(ListNodehead){ListNodeslow=head;ListNodefast=head.next;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}// 断开链表，分成两个ListNodetemp=slow.next;slow.next=null;returntemp;}// 双指针合并两个链表privateListNodemergeList(ListNodehead,ListNodehead2){ListNodep1=head;ListNodep2=head2;ListNodep=newListNode(0);ListNodepre=p;while(p1!=null&&p2!=null){if(p1.val>p2.val){pre.next=p2;p2=p2.next;}else{pre.next=p1;p1=p1.next;}pre=pre.next;}pre.next=p1!=null?p1:p2;returnp.next;}}