题目：

148. 排序链表

题解：

归并排序的基本思想是： 找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。

1. 题解一：归并排序（递归法）（首选）

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

2. 题解二：归并排序（从底至顶直接合并）

current = dummy.next; tail = dummy; for (step = 1; step < length; step *= 2) { while (current) { // left->@->@->@->@->@->@->null left = current; // left->@->@->null right->@->@->@->@->null right = cut(current, step); // 将 current 切掉前 step 个头切下来。 // left->@->@->null right->@->@->null current->@->@->null current = cut(right, step); // 将 right 切掉前 step 个头切下来。 // dummy.next -> @->@->@->@->null，最后一个节点是 tail，始终记录 // ^ // tail tail.next = merge(left, right); while (tail->next) tail = tail->next; // 保持 tail 为尾部 } }

代码：

1. 代码一：归并排序（递归法）（首选）

public class code148_1 { // 时间复杂度: O(nlogn) // 空间复杂度: O(logn) // 自顶向下 public static ListNode sortList(ListNode head) { // 1、递归结束条件 // 当链表为空或者链表只剩下一个结点时，直接返回 head if(head == null || head.next == null) { return head; } // 2、找到链表中间节点并断开链表 & 递归下探 ListNode midNode = middleNode(head); // 得到中间节点 midNode，从中间cut ListNode rightHead = midNode.next; // 将第一个链表的结尾（midNode位置的下一个节点）置为空，实现切断 midNode.next = null; // 递归对cut后的子链表排序 ListNode left = sortList(head); ListNode right = sortList(rightHead); // 3、当前层业务操作（合并有序链表） // 比较合并两个有序链表 return mergeTwoLists(left, right); } // 找到链表中间节点（876. 链表的中间结点） public static ListNode middleNode(ListNode head) { if(head == null) { return null; } ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null) { // fast 一次前进两个元素，slow 一次前进一个元素 slow = slow.next; fast = fast.next.next; } // 链表元素为奇数个时，slow 指向链表的中点 // 链表元素为偶数个时，slow 指向链表两个中点的左边一个 return slow; } // 合并两个有序链表（21. 合并两个有序链表） public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 类似归并排序中的合并过程 ListNode dummy = new ListNode(0); ListNode cur = dummy; while(l1 != null && l2 != null) { if(l1.val < l2.val) { cur.next = l1; cur = cur.next; l1 = l1.next; } else { cur.next = l2; cur = cur.next; l2 = l2.next; } } // 任一为空，直接连接另一条链表 if(l1 == null) { cur.next = l2; } else { cur.next = l1; } return dummy.next; } private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中 if (arr.length == 0) { return null; } ListNode head = new ListNode(arr[0]); ListNode current = head; for (int i = 1; i < arr.length; i++) {// 过程 current.next = new ListNode(arr[i]); current = current.next; } return head; } private static void printLinkedList(ListNode head) {// 将链表结果打印 ListNode current = head; while (current != null) { System.out.printf("%d -> ", current.val); current = current.next; } System.out.println("NULL"); } public static void main(String[] args) { int[] x1 = { 4, 2, 1, 3 }; ListNode list1 = createLinkedList(x1); printLinkedList(list1); ListNode res1 = sortList(list1); printLinkedList(res1); System.out.println("***************************************"); int[] x2 = { -1, 5, 3, 4, 0 }; ListNode list2 = createLinkedList(x2); printLinkedList(list2); ListNode res2 = sortList(list2); printLinkedList(res2); } }

2. 代码二：归并排序（从底至顶直接合并）

public class code148_2 { // 时间复杂度: O(nlogn) // 空间复杂度: O(1) // 从底至顶直接合并 public static ListNode sortList(ListNode head) { ListNode dummyHead = new ListNode(Integer.MIN_VALUE); dummyHead.next = head; // 先统计长度f ListNode p = dummyHead.next; int length = 0; while (p != null) { ++length; p = p.next; } // 循环开始切割和合并 for (int size = 1; size < length; size <<= 1) { ListNode cur = dummyHead.next; ListNode tail = dummyHead; while (cur != null) { ListNode left = cur; ListNode right = cut(cur, size); // 链表切掉size 剩下的返还给right cur = cut(right, size); // 链表切掉size 剩下的返还给cur tail.next = merge(left, right); while (tail.next != null) { tail = tail.next; // 保持最尾端 } } } return dummyHead.next; } /** * 将链表L切掉前n个节点 并返回后半部分的链表头 * * @param head * @param n * @return */ public static ListNode cut(ListNode head, int n) { if (n <= 0) return head; ListNode p = head; // 往前走n-1步 while (--n > 0 && p != null) { p = p.next; } if (p == null) return null; ListNode next = p.next; p.next = null; return next; } /** * 合并list1和list2 * * @param list1 * @param list2 * @return */ public static ListNode merge(ListNode list1, ListNode list2) { ListNode dummyHead = new ListNode(Integer.MIN_VALUE), p = dummyHead; while (list1 != null && list2 != null) { if (list1.val < list2.val) { p.next = list1; list1 = list1.next; } else { p.next = list2; list2 = list2.next; } p = p.next; } if (list1 == null) { p.next = list2; } else { p.next = list1; } return dummyHead.next; } private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中 if (arr.length == 0) { return null; } ListNode head = new ListNode(arr[0]); ListNode current = head; for (int i = 1; i < arr.length; i++) {// 过程 current.next = new ListNode(arr[i]); current = current.next; } return head; } private static void printLinkedList(ListNode head) {// 将链表结果打印 ListNode current = head; while (current != null) { System.out.printf("%d -> ", current.val); current = current.next; } System.out.println("NULL"); } public static void main(String[] args) { int[] x1 = { 4, 2, 1, 3 }; ListNode list1 = createLinkedList(x1); printLinkedList(list1); ListNode res1 = sortList(list1); printLinkedList(res1); System.out.println("***************************************"); int[] x2 = { -1, 5, 3, 4, 0 }; ListNode list2 = createLinkedList(x2); printLinkedList(list2); ListNode res2 = sortList(list2); printLinkedList(res2); } }

参考：

Sort List （归并排序链表）148. 排序链表-bottom-to-up O(1) 空间Sort List——经典（链表中的归并排序）