1.插入排序链表（147-中）
问题描述：插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
案例：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
思路：本题基本思路是插入排序，如何维护已排序链表，如何遍历剩余链表？两个关键问题：
lastSorted：维护已经排好序链表的最后一个节点cur：遍历剩余链表待插入节点
注意：对于一般情况，我们需要从头遍历已经排好序的链表，找到该位置，然后重连。
代码:
public ListNode insertionSortList(ListNode head) { if (head == null) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode lastSorted = head; // 已经排好序链表的最后一个节点 ListNode cur = head.next; //待插入的节点 while (cur != null) { if (lastSorted.val <= cur.val) { lastSorted = lastSorted.next; } else { ListNode pre = dummy; while (pre.next.val <= cur.val) { pre = pre.next; } lastSorted.next = cur.next; // 取出待插入节点 cur.next = pre.next; pre.next = cur; } cur = lastSorted.next; } return dummy.next; }
注意：时间复杂度O(n^2)
2.归并排序链表（148-中）
问题描述：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。要求：O(n log n) 时间复杂度和常数级空间复杂度。
案例：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
思路：根据要求这里使用归并排序进行求解。时间复杂度O(n log n) ，基本流程：
- 快慢指针找到链表的中点
- 对左右分区进行递归
- 遍历链表，比较连接
代码:
public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // 将两个链表平均分开 ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next; slow.next = null; // 拆分 ListNode left = sortList(head); ListNode right = sortList(tmp); // 合并 ListNode dummy = new ListNode(0); ListNode cur = dummy; 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; } cur.next = left != null ? left : right; return dummy.next; }
3.快速排序链表
思路：快排实现思路，选取基准值遍历链表，比基准值小的进行头插，大于基准值的尾插：
- lhead维护的是小于基准值的头插指针
- utail维护的是大于等于基准值的尾插指针
然后对这两部分链表进行分治，保证区间不变性：
[ lhead , head )是小于基准值的一部分[ head.next , end )是大于等于基准值的一部分
代码:
public ListNode sortList(ListNode head) { return quickSort(head, null); } private ListNode quickSort(ListNode head, ListNode end) { if (head == end || head.next == end) return head; ListNode Ihead = head, utail = head, cur = head.next; while (cur != end) { ListNode next = cur.next; if (cur.val < head.val) { cur.next = Ihead; Ihead = cur; } else { utail.next = cur; utail = cur; } cur = next; } utail.next = end; ListNode node = quickSort(Ihead, head); head.next = quickSort(head.next, end); return node; }
也可以设置三个虚拟节点，类似荷兰国旗（即小于等于或者大于给定值）对链表进行递归拆分，最后拼接。代码如下：
public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode lowDummy = new ListNode(0); ListNode low = lowDummy; ListNode equalDummy = new ListNode(0); ListNode equal = equalDummy; ListNode highDummy = new ListNode(0); ListNode high = highDummy; // 遍历链表，进行分区（partition） ListNode cur = head; while (cur != null) { if(cur.val < head.val) { low.next = cur; low = low.next; } else if (cur.val == head.val) { equal.next = cur; equal = equal.next; } else { high.next = cur; high = high.next; } cur = cur.next; } // 避免递归过程中成环 low.next = null; high.next = null; lowDummy.next = sortList(lowDummy.next); highDummy.next = sortList(highDummy.next); // 连接三部分 low = lowDummy; while (low.next != null) { low = low.next; } low.next = equalDummy.next; equal.next = highDummy.next; return lowDummy.next; }
另外根据快排思想可以对值进行交换，但有些题目不允许这么做。
public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; quickSort(head, null); return head; } private void quickSort(ListNode begin, ListNode end) { if (begin != end && begin.next != end) { ListNode node = partition(begin, end); quickSort(begin, node); quickSort(node.next, end); } } private ListNode partition(ListNode head, ListNode end) { ListNode p1 = head, p2 = head.next; while (p2 != end) { if (p2.val < head.val) { p1 = p1.next; swap(p1, p2); } p2 = p2.next; } swap(p1, head); return p1; } private void swap(ListNode i, ListNode j) { int tmp = i.val; i.val = j.val; j.val = tmp; }
注意：快排链表在Leetcode运行时间都比较长，有时会超时，不知道为什么，希望大佬们指教。
总之，排序链表首选归并排序，时间复杂度稳定在O(nlogn)；如果用快速排序可以使用上述中的第一种，但由于单链表不能随意获取划分值pivot，时间复杂度可能退化为O(nlogn)。
4.排序奇升偶降链表（字节高频题）
问题描述：给定一个奇数位升序，偶数位降序的链表，将其重新排序。不能使用额外空间。
案例：
输入: 1->8->3->6->5->4->7->2->NULL 输出: 1->2->3->4->5->6->7->8->NULL
思路：核心主要分为以下三步：
- 按照奇偶位置拆分链表（leetcode328）
- 反转偶链表（leetcode206）
- 合并两个有序链表（leetcode21）
ps：在拆分链表时遇到一个坑，一定要 odd.next = null， 否则出现死循环
代码:
public class Solution002 { public static class ListNode { int val; ListNode next; public ListNode() { } public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static void main(String[] args) { // 测试 1->4->3->2->NULL ListNode node = new ListNode(1); node.next = new ListNode(4); node.next.next = new ListNode(3); node.next.next.next = new ListNode(2); ListNode sortedNode = sort(node); while (sortedNode != null) { System.out.print(sortedNode.val + " "); sortedNode = sortedNode.next; } } public static ListNode sort(ListNode head) { // 1.根据奇偶数位拆分链表 ListNode oddHead = split(head); // 2.反转偶数位链表 ListNode newEvenHead = reverse(evenHead); // 3.拼接两个有序链表 ListNode sortedNode = merge(oddHead, newEvenHead); return sortedNode; } public static ListNode evenHead; public static ListNode split(ListNode head) { ListNode odd = head, even = head.next; evenHead = even; while (even != null && even.next != null) { odd.next = odd.next.next; odd = odd.next; even.next = even.next.next; even = even.next; } // odd.next = evenHead; t328：尾部连接 odd.next = null; return head; } public static ListNode reverse(ListNode head) { ListNode pre = null, next; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } public static ListNode merge(ListNode l1, ListNode l2) { ListNode pre = new ListNode(-1); ListNode cur = pre; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null) ? l2 : l1; return pre.next; } }
