⭐ 题目日期：

快手 - 2024/12/13, 百度 - 2024/10/19

🌳 题目描述：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L(0) → L(1) → … → L(n - 1) → L(n)

请将其重新排列后变为：

L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → …

不能只是单纯地改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

🧗难度系数：

⭐️ ⭐️ ⭐️️ ⭐️

📝思路分析：

重排之后的链表：

L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → …

显而易见，新链表由之前链表的节点相互交错排列，我们抽离交错的节点，还原得到：

L(0) → L(1) → L(2) → …

L(n) → L(n - 1) → L(n - 2) → …

L(0) → L(1) → L(2) → … 为原链表的排列，L(n) → L(n - 1) → L(n - 2) → … 似曾相识，如果反转：

...→L(n - 2) → L(n - 1) → L(n) 为原链表的后半部分。

至此，我们有了一些思路：

1. 将原链表分成两半
2. 前半部分顺序保持不变，后半部分反转
3. 再将两链表交错合并，得到新链表

🌟 将原链表分成两半的核心操作为定位中间的节点，找到链表中某一个特定的位置通常有两种方法：

1. 快慢指针，根据题目的要求确定快慢指针的初始距离，使得当快指针走完链表，慢指针刚好落在目标位置上
2. 先遍历链表拿到长度，再通过简单的数学计算算出走多少步能到目标节点。

对比：

1. 从复杂度的角度，两种方法的效率是一样的，空间复杂度都为O(1)；时间复杂度的角度，虽然快慢指针法只遍历了一遍链表，但是每次都要操作两个指针，时间复杂度为O(2n), 与方法2基本持平。
2. 即使复杂度类似，快慢指针的巧妙为这种算法增添了不少光彩，因此很多面试官可能会要求你会这种“高级”算法，并且能说出除复杂度之外的优点：1. 只遍历了链表一次。2. 代码实现相对简单

💻代码：

Java

 public void reorderList(ListNode head) {
     if (head == null || head.next == null) {
         return;
     }

     // 1. 使用快慢指针找到链表的中间节点
     ListNode slow = head;
     ListNode fast = head;
     while (fast.next != null && fast.next.next != null) {
         slow = slow.next;
         fast = fast.next.next;
     }

     // 2. 反转从中间节点断开的后半部分链表
     ListNode secondHalf = reverseList(slow.next);

     // 至此 slow 为中间节点，断开第一部分和第二部分
     slow.next = null; 

     // 3. 合并两个链表
     ListNode firstHalf = head;
     ListNode dummyNode = new ListNode(0);
     ListNode cur = dummyNode;
     while (secondHalf != null) {
         cur.next = firstHalf;
         firstHalf = firstHalf.next;
         cur = cur.next;

         cur.next = secondHalf;
         secondHalf = secondHalf.next;
         cur = cur.next;
     }

     // 可能链表的长度为奇数，最后剩一个节点需要连接上
     cur.next = firstHalf;
 }

 private ListNode reverseList(ListNode head) {
     ListNode prev = null;
     while (head != null) {
         ListNode nextNode = head.next;
         head.next = prev;
         prev = head;
         head = nextNode;
     }
     return prev;
 }

🚵🏻复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)

题目链接