Problem: 148. 排序鏈表

思路

這是一個(gè)鏈表排序的問題，由于要求時(shí)間復(fù)雜度為 O(nlogn)，適合使用歸并排序（Merge Sort）來解決。

解題方法

1. 首先，使用快慢指針找到鏈表的中間節(jié)點(diǎn)，將鏈表分成兩部分。
2. 然后，遞歸地對(duì)兩個(gè)子鏈表進(jìn)行排序。
3. 最后，合并兩個(gè)有序的子鏈表。

復(fù)雜度

時(shí)間復(fù)雜度: O(nlogn)
空間復(fù)雜度: O(logn)（遞歸調(diào)用棧的深度）

Code

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode slow = head;ListNode fast = head;while(fast.next != null && fast.next.next != null) {slow= slow.next;fast = fast.next.next;}ListNode mid = slow.next;slow.next = null;ListNode left = sortList(head);ListNode right = sortList(mid);return mergeList(left, right);}private ListNode mergeList(ListNode left, ListNode right) {ListNode dummyHead = new ListNode(-1);ListNode cur = dummyHead;while(left != null && right != null) {if(left.val < right.val) {cur.next = left;left = left.next;}else{cur.next = right;right = right.next;}cur = cur.next;}if(left == null) {cur.next = right;}if(right == null) {cur.next = left;}return dummyHead.next;}
}