LeetCode 143.重排链表

1.题目要求：将原链表重排序为：第一个节点->最后一个节点->第二个节点->倒数第二个节点->第三个节点->倒数第三个节点...。

2.思路：

以1->2->3->4->5为例。

（1）找到链表的中间节点middleNode：快慢指针法，找到中间节点mid = 3。

（2）翻转后半部分的链表reverseList：从中点开始反转后半部分的链表。反转后：1->2->3，5->4->3（注意3是共享节点）。

（3）交错合并：两个链表的节点从前往后逐个交错合并。

3.复杂度分析：

（1）时间复杂度：O(n)，其中n为链表的长度。

（2）空间复杂度：O(1)，仅用到若干额外变量。

4.疑问：循环条件while head2.next为什么不能写成while head2？（在hot100 234.回文链表中是while(head 2!=null)，这里却是while(head2.next != null)）

答：

这里不用head2 != null是为了防止形成环， 由于mid节点是重排链表后的最后一个节点，因此当head2刚走到mid时：

（1）要么此时head1也指向mid（此时对应于链表是奇数的情况）

（2）要么此时head1指向mid节点的前一个节点（对应于链表是偶数的情况）

无论哪种情况都表明这个链表已经在head2刚走到mid时重排完成，因此可以直接退出循环，再继续循环到head2 == null会形成环。

附代码：

class Solution { public void reorderList(ListNode head) { ListNode mid = middleNode(head); ListNode head2 = reverseList(mid); // 这里不用head2 != null是为了防止形成环 // 由于mid节点是重排链表后的最后一个节点 // 因此当head2刚走到mid时 // （1）要么此时head1也指向mid（此时对应于链表是奇数的情况） // （2）要么此时head1指向mid节点的前一个节点（对应于链表是偶数的情况） // 无论哪种情况都表明这个链表已经重排完成，因此可以直接退出循环，再继续循环下去会形成环 while(head2.next != null){ ListNode next1 = head.next; ListNode next2 = head2.next; head.next = head2; head2.next = next1; head = next1; head2 = next2; } } // 876.链表的中间节点,快慢指针法 private ListNode middleNode(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } // 206.反转链表 private ListNode reverseList(ListNode head){ ListNode pre = null; ListNode cur = head; while(cur != null){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }

ACM模式：

import java.util.Scanner; // 将 ListNode 定义为独立的类 class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; this.next = null; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取链表长度 int n = scanner.nextInt(); // 读取链表元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 创建链表 ListNode head = null; if (n > 0) { head = new ListNode(nums[0]); ListNode current = head; for (int i = 1; i < n; i++) { current.next = new ListNode(nums[i]); current = current.next; } } // 调用重排链表方法 Solution solution = new Solution(); solution.reorderList(head); // 输出重排后的链表 if (head == null) { System.out.println(""); } else { ListNode current = head; while (current != null) { System.out.print(current.val); if (current.next != null) { System.out.print(" "); } current = current.next; } System.out.println(); } scanner.close(); } } // 重排链表方法放在 Solution 类中 class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } ListNode mid = middleNode(head); ListNode head2 = reverseList(mid); while (head2.next != null) { ListNode next1 = head.next; ListNode next2 = head2.next; head.next = head2; head2.next = next1; head = next1; head2 = next2; } } // 876. 链表的中间节点，快慢指针法 private ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 206. 反转链表 private ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }