1+ // 143. 重排链表
2+
3+
4+ /**
5+ * Definition for singly-linked list.
6+ * public class ListNode {
7+ * int val;
8+ * ListNode next;
9+ * ListNode() {}
10+ * ListNode(int val) { this.val = val; }
11+ * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
12+ * }
13+ */
14+
15+
16+ /*
17+ 注意：不是使用第三个链表去重新连接原链表，而是直接获取原链表节点改变其指针指向
18+ 1、使用列表存放节点，双指针从头尾取节点，改变节点连接顺序
19+ 2、left、right指针指向的节点表示 准备用来修改它的下一指针方向的节点
20+ 3、奇数个节点时，最后一次指针移动是right指针左移，此时 left == right 进入不了下一轮循环
21+ 偶数个节点时，最后一次指针移动是left指针右移，此时 left == right，由于程序下面还有右指针节点处理逻辑，所以需要提前跳出循环
22+
23+ 1 2 3 1 2 3 4
24+ ↑ ↑ ↑ ↑
25+ left right left right
26+
27+ 1 2 3 4 5 6 7
28+ left right
29+ ==============================
30+ 1 2 3 4 5 6 7
31+ left right
32+ ==============================
33+ 1 → 7 → 2
34+ */
35+ class Solution {
36+ public void reorderList (ListNode head ) {
37+ List <ListNode > list = new ArrayList <>();
38+ while (head != null ) {
39+ list .add (head );
40+ head = head .next ;
41+ }
42+ int left = 0 , right = list .size () - 1 ;
43+ while (left < right ) {
44+ list .get (left ).next = list .get (right );
45+ left ++;
46+ if (left == right ) {
47+ break ;
48+ }
49+ list .get (right ).next = list .get (left );
50+ right --;
51+ }
52+ list .get (left ).next = null ;
53+ }
54+ }
55+
56+
57+ /*
58+ 思路：利用快慢指针找到链表中点，链表后半部分反转得到新链表，两个链表从头开始改变对应节点指针方向
59+ 1、前三个节点为空则直接结束，因为交换至少需要三个节点
60+ 2、快慢指针从头节点开始，慢指针每次走一步，快指针每次走两步。
61+ 快指针遇到空时说明走到末尾了，fast.next为空是奇数个节点的情况，fast.next.next为空是偶数个节点的情况
62+ 3、后半部分链表反转，前半部分尾部断开，形成两个链表
63+ 4、两个链表从头开始，改变对应节点的指针方向
64+
65+ 1 → 2 → 3 → 4 → 5 → 6 → 7
66+ head/slow/fast
67+ ====================================================
68+ 1 → 2 → 3 → 4 → 5 → 6 → 7
69+ head slow fast
70+ ====================================================
71+ 1 → 2 → 3 → 4 7 → 6 → 5
72+ head newHead newHeadNext
73+ ====================================================
74+ 1 → 7 → 2 → 3 → 4 6 → 5
75+ head newHead newHeadNext
76+ ====================================================
77+ 1 → 7 → 2 → 3 → 4 6 → 5
78+ head newHead newHeadNext
79+ */
80+ class Solution {
81+ public void reorderList (ListNode head ) {
82+ if (head == null || head .next == null || head .next .next == null ) {
83+ return ;
84+ }
85+ ListNode slow = head , fast = head ;
86+ while (fast .next != null && fast .next .next != null ) {
87+ slow = slow .next ;
88+ fast = fast .next .next ;
89+ }
90+ ListNode newHead = reverse (slow .next );
91+ slow .next = null ;
92+ while (newHead != null ) {
93+ ListNode newHeadNext = newHead .next ;
94+ newHead .next = head .next ;
95+ head .next = newHead ;
96+ head = newHead .next ;
97+ newHead = newHeadNext ;
98+ }
99+ }
100+
101+ // 206.反转链表
102+ private ListNode reverse (ListNode head ) {
103+ ListNode before = null , after ;
104+ while (head != null ) {
105+ after = head .next ;
106+ head .next = before ;
107+ before = head ;
108+ head = after ;
109+ }
110+ return before ;
111+ }
112+ }
0 commit comments