這道題可以拆分為兩道算法題，分別是：[鏈表的中間結點] 和 [反轉鏈表]。
鏈表的中間結點（雙指針）#
借助快慢雙指針 fast 和 slow，[快指針 fast ] 每輪走 2 步，[慢指針 slow ] 每輪走 1 步。
fast 的步數恒為 slow 的 2 倍，因此當快指針遍歷完鏈表時，慢指針就指向鏈表中間節點。而由於長度為偶數的鏈表有兩個中間節點，因此需要分兩種情況考慮：
- 鏈表長度為奇數：當
fast走到鏈表 [尾節點] 時，slow正好走到 [中間節點]。 - 鏈表長度為偶數：當
fast走到 [null] 時（越過 [尾節點] 後），slow正好走到 [第二個中間節點]。
總結以上規律，應該在 fast 遇到或越過尾節點時跳出循環，並返回 slow 即可。
// 長度為奇數的鏈表
ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
// 長度為偶數的鏈表
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));
Console.WriteLine("odd head middleNode val: {0}", MiddleNode(oddHead).Val);
Console.WriteLine("even head middleNode val: {0}", MiddleNode(evenHead).Val);
// 鏈表的中間結點
ListNode MiddleNode(ListNode head)
{
// 初始化快慢指針 fast, slow 皆指向鏈表頭節點 head
ListNode? fast = head, slow = head;
// 當 fast 遇到過越過尾節點時跳出循環
while (fast != null && fast.Next != null)
{
fast = fast.Next.Next;
slow = slow!.Next;
}
return slow!;
}
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}
若題目要求返回「第一個中間節點」，則應在 fast 遇到尾節點或其前驅節點 時跳出循環。此時，修改判斷條件為 while fast.next and fast.next.next 即可。
反轉鏈表#
解法一：迭代（雙指針）#
遍歷鏈表，並在訪問各節點時修改 next 引用指向，具體流程看代碼註釋。
// 初始化鏈表
ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
ListNode reverseNode = ReverseNode(node);
while (reverseNode != null)
{
Console.WriteLine("reverseNode val: {0}", reverseNode.Val);
reverseNode = reverseNode.Next;
}
// 反轉鏈表：迭代（雙指針）
ListNode ReverseNode(ListNode head)
{
// 初始化 pre, cur 分別指向 null 和 頭節點
ListNode pre = null, cur = head;
while (cur != null)
{
ListNode tmp = cur.Next; // 暫存後繼節點
cur.Next = pre; // 修改引用指向
pre = cur; // 暫存當前節點
cur = tmp; // 訪問下一節點
}
return pre;
}
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}
最終代碼#
// Q: 鏈表取前一半翻轉，再跟後一半連接
// 初始化長度為奇數的鏈表
using System.Diagnostics;
ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
// 初始化長度為偶數的鏈表
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));
// 按照要求將鏈表取前一半翻轉，再跟後一半連接後的鏈表
Console.WriteLine("長度為奇數的鏈表：");
Stopwatch sw = Stopwatch.StartNew();
ListNode? finalOddHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(oddHead);
sw.Stop();
Console.WriteLine($"耗時: {sw.ElapsedMilliseconds}ms");
while (finalOddHead != null)
{
Console.WriteLine(finalOddHead.Val);
finalOddHead = finalOddHead.Next;
}
// 按照要求將鏈表取前一半翻轉，再跟後一半連接後的鏈表
Console.WriteLine("長度為偶數的鏈表：");
sw = Stopwatch.StartNew();
ListNode? finalEvenHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(evenHead);
sw.Stop();
Console.WriteLine($"耗時: {sw.ElapsedMilliseconds}ms");
while (finalEvenHead != null)
{
Console.WriteLine(finalEvenHead.Val);
finalEvenHead = finalEvenHead.Next;
}
ListNode ReverseLeftOfMiddleAndCombineRightOfMiddle(ListNode head)
{
// 找到鏈表的中點
// 使用快慢指針 fast 和 slow，快指針每次走 2 步，快指針的步數恒為慢指針的 2 倍，慢指針每次走一步，當快指針遇到或越過尾節點時跳出循環，返回 slow 即可，其代表中間節點。
ListNode fast = head, slow = head;
while (fast != null && fast.Next != null)
{
fast = fast.Next.Next;
slow = slow.Next;
}
// 當鏈表長度為奇數時，slow 剛好是最中間的節點
// 當鏈表長度為偶數時，slow 是中間兩個節點的最後一個節點
ListNode middleNode = slow;
// 翻轉左側鏈表
// 使用迭代（雙指針）
// 這裡將 pre 指向中點，這樣最後翻轉左側鏈表後，左側鏈表的最後一個節點就指向右側鏈表（鏈表中點），就實現將翻轉後鏈表的和右側鏈表連接
ListNode pre = middleNode, cur = head;
// 當前循環的節點不為空，並且當前循環的節點在中點之前，即只翻轉中點左側的鏈表
while (cur != null && cur.Val != middleNode.Val)
{
// 暫存後繼節點
ListNode tmp = cur.Next;
// 修改引用指向
cur.Next = pre;
// 暫存當前節點
pre = cur;
// 訪問下個節點
cur = tmp;
}
return pre;
}
// 單向鏈表結構
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}