O(1)空间复杂度下求单链表首尾逐次配对求和的最大值

你之前的思路每次遍历都要找当前尾节点，总时间复杂度为O(n²)，确实存在较大优化空间，以下是时间复杂度O(n)、空间复杂度仍为O(1)的实现方案，完全符合题目要求：

核心思路 #

本质上我们要计算的配对是：原链表第1个和最后1个、第2个和倒数第2个……第k个和倒数第k个的和的最大值。我们不需要动态删除首尾节点，只需要通过「找中点+反转后半段」的操作，把反向遍历后半段的需求变成正向遍历，就能用双指针一次遍历完成计算。

具体实现步骤 #

• 第一步：快慢指针定位链表中点
  初始化快、慢指针都指向链表头节点，快指针每次移动2步，慢指针每次移动1步，直到快指针的后继节点为空（链表总长度为偶数，此时快指针刚好停在最后一个节点，慢指针停在前半段的最后一个节点），此时后半段的头节点为慢指针的后继节点。
• 第二步：原地反转后半段链表
  仅通过修改节点指针的方式反转后半段链表，不需要额外存储空间，反转完成后后半段的头节点就是原链表的尾节点。
• 第三步：双指针遍历计算最大和
  左指针从原链表头节点出发，右指针从反转后的后半段头节点出发，两个指针每次同步移动1步，每次计算当前两个指针指向节点的数值和，更新全局最大值，直到右指针遍历到空节点为止（前后半段长度相等，刚好完成所有配对计算）。

复杂度说明 #

• 时间复杂度：找中点、反转后半段、双指针遍历三个步骤都是O(n)的时间开销，总时间复杂度为O(n)，远优于原来的O(n²)方案
• 空间复杂度：全程仅使用常数个额外指针，空间复杂度为O(1)，符合题目要求

举个简单验证例子：原链表为2->3->5->1->4->6，中点在5的位置，后半段1->4->6反转后为6->4->1，配对和分别为2+6=8、3+4=7、5+1=6，最大值为8，和动态删除首尾节点的计算结果完全一致。

内容的提问来源于stack exchange，提问作者daniel