这道题可以拆分为两道算法题，分别是：[链表的中间结点] 和 [反转链表]。
链表的中间结点（双指针）#
借助快慢双指针 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;
}
}