【算法训练-链表 七】【排序】：链表排序、链表的奇偶重排、重排链表

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【链表的排序】，使用【链表】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

以及重排链表

附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

链表排序【MID】

单链表的升序排列

题干

解题思路

而链表中我们也可以用【合并K个有序链表】同样的方式，当链表被划分到只剩一个节点时，就一定有序。只需要找到中间个元素的前一个节点，将其断开，就可以将链表分成两个子链表，然后继续划分，直到最小，然后往上依次合并。

• 终止条件： 当子链表划分到为空或者只剩一个节点时，不再继续划分，往上合并。
• 返回值： 每次返回两个排好序且合并好的子链表。
• 本级任务： 找到这个链表的中间节点，从前面断开，分为左右两个子链表，进入子问题排序。

怎么找中间元素呢？我们可以使用快慢双指针，快指针每次两步，慢指针每次一步，那么快指针到达链表尾的时候，慢指针正好走了快指针距离的一半，为中间元素。

具体做法：

1. step 1【入参判断】：首先判断链表为空或者只有一个元素，直接就是有序的。
2. step 2【找中间节点】：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
3. step 3【划分子问题】：从left位置将链表断开，刚好分成两个子问题开始递归。
4. step 4【合并子问题】：将子问题得到的链表合并，参考合并两个有序链表。

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：分治
技巧：双指针（快慢指针）

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类 the head node* @return ListNode类*/public ListNode sortInList (ListNode head) {// 1 入参判断，如果链表只剩一个节点或者空，则直接有序，到达终止条件if (head == null || head.next == null) {return head;}// 2 中间位置为慢指针的下一个节点，奇数节点链表为正中间，偶数则为另一半的开头，所以后半段一定是mid.nextListNode mid= findMidNode(head);// 3 设置后半段链表，断开前后半段链表ListNode newHead = mid.next;mid.next = null;// 4 合并两段有序链表return mergeSortList(sortInList(head), sortInList(newHead));}// 寻找链表中间节点private ListNode findMidNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}// 3 中间位置为慢指针的下一个节点，奇数节点链表为正中间，偶数则为另一半的开头return slow;}// 合并两个有序链表private ListNode mergeSortList(ListNode pHead1, ListNode pHead2) {// 1 入参判断if (pHead1 == null && pHead2 == null) {return null;}if (pHead1 == null) {return pHead2;}if (pHead2 == null) {return pHead1;}// 2 设置结果链表ListNode dummy = new ListNode(-1);ListNode p = dummy;while (pHead1 != null && pHead2 != null) {if (pHead1.val <= pHead2.val) {p.next = pHead1;pHead1 = pHead1.next;} else {p.next = pHead2;pHead2 = pHead2.next;}p = p.next;}// 3 如果其中一个链表为空，后续直接接另一个if (pHead1 == null) {p.next = pHead2;}if (pHead2 == null) {p.next = pHead1;}return dummy.next;}
}

复杂度分析

链表的奇偶重排【MID】

需要注意的是节点的位置而非节点的值

题干

解题思路

核心思路就是奇数位节点和偶数位节点断掉重连

1. step 1：判断空链表的情况，如果链表为空，不用重排。如果链表只有一个节点也不用重排
2. step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
3. step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环行上述连接过程。
4. step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针（同向指针）

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @return ListNode类*/public ListNode oddEvenList (ListNode head) {// 1 入参条件判断if (head == null) {return null;}if (head.next == null) {// 只有1个节点，不用重排return head;}// 2 设置偶数虚拟头节点,并设定奇偶双指针ListNode odd = head;ListNode evenDummy = head.next;ListNode even = evenDummy;// 3 遍历链表，往奇数和偶数节点上补充对应节点,因为even在后边，所以要以even做判断，否则对于1-2-3-4这种情况//odd结束时指向null，null.next会有问题，返回仍然是nullwhile (even != null && even.next != null) {// 奇数位断开指向偶数的指针并指向下一个奇数位odd.next = even.next;odd = odd.next;// 偶数位断开指向奇数的指针并指向下一个偶数位even.next = odd.next;even = even.next;}// 4 遍历完后偶数整体接到奇数后odd.next = evenDummy;return head;}
}

复杂度分析

时间复杂度：O(n)，遍历一次链表的所有节点
空间复杂度：O(1)，常数级指针，无额外辅助空间

重排链表【MID】

复杂度升级了一些，不过套路类似

题干

解题思路

注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样我们的任务即可划分为三步：

1. 【找到中点】找到原链表的中点（参考「876. 链表的中间结点」）。我们可以使用快慢指针来 O(N)O(N)O(N) 地找到链表的中间节点。
2. 【反转右半边】将原链表的右半端反转（参考「206. 反转链表」）。我们可以使用迭代法实现链表的反转。
3. 【合并两个链表】将原链表的两端合并。因为两链表长度相差不超过 11，因此直接合并即可。

以上需要注意的是，找链表中点时，对于奇数个节点，中点为前半段链表所有（从题目示例可以看出）

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

/*** 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 void reorderList(ListNode head) {// 1 入参校验if (head == null || head.next == null) {return ;}// 2 找到链表中点，断开后半段链表，这次要找的mid要偏右一些，前半段保留偏长，这样后续交替衔接才没问题ListNode mid = middleNode(head);ListNode l1 = head;ListNode l2 = mid.next;mid.next = null;// 3 反转后半段链表l2 = reverse(l2);// 4 将反转后链表连接到原链表中mergeList(l1, l2);}// 交替合并两个链表private void mergeList(ListNode l1, ListNode l2) {ListNode pNext1;ListNode pNext2;// 因为两个链表仅仅相差1，所以直接交替合并即可while (l1 != null && l2 != null) {// 暂存两个链表的下一个节点pNext1 = l1.next;pNext2 = l2.next;// 交替衔接l1和l2l1.next = l2;l1 = pNext1;l2.next = l1;l2 = pNext2;}}// 寻找中间节点private ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 反转链表private ListNode reverse(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode pNext = cur.next;cur.next = pre;pre = cur;cur = pNext;}return pre;}
}

复杂度分析

时间复杂度：遍历了链表，时间复杂度为O（N）
空间复杂度：没有使用额外空间，空间复杂度为O（1）