力扣-链表最大孪生和

思路分析

1. 找链表中点：用快慢指针（慢指针走 1 步，快指针走 2 步）找到链表的中间节点；
2. 反转后半段链表：将中点后的后半段链表反转；
3. 计算孪生和：用两个指针分别从链表头部和反转后的后半段头部出发，依次计算每对孪生节点的和，记录最大值。

代码实现

/** * 方法一：快慢指针找到中间节点，反转后半部分链表，遍历两部分节点计算最大和 * @param head * @return */publicintpairSum(ListNodehead){// 快慢指针找到中间节点ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}// 反转后半部分链表ListNodereverseHead=reverseListNode(slow);// 遍历两部分节点计算最大和intmaxSum=0;while(reverseHead!=null){intfirstNum=head.val;intsecondNum=reverseHead.val;maxSum=Math.max(maxSum,firstNum+secondNum);head=head.next;reverseHead=reverseHead.next;}returnmaxSum;}/** * @Author Feng * @Description * @Date 2026/1/14 * @Param [slow] * @return main.leetcode75.arr_str.entity.ListNode **/privateListNodereverseListNode(ListNodehead){// 定义前一个节点为null，当前节点为头节点ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodetemp=curr.next;curr.next=prev;prev=curr;curr=temp;}returnprev;}

复杂度分析

• 空间复杂度 O (1)：无需额外存储所有节点值，仅用指针操作；
• 时间复杂度 O (n)：找中点 O (n/2) + 反转后半段 O (n/2) + 计算和 O (n/2)，总复杂度 O (n)。

思路分析二

1. 使用快慢指针找中点：

   • 使用快慢指针技术找到链表的中间节点
   • 慢指针每次移动一步，快指针每次移动两步
   • 当快指针到达末尾时，慢指针正好在链表的中点位置

2. 利用栈存储前半部分节点值：

   • 创建一个双端队列（用作栈）
   • 从头节点开始遍历到中点之前的所有节点
   • 将这些节点的值依次压入栈中
   • 由于栈是后进先出的数据结构，这样栈顶元素对应的是链表后半部分对称位置的节点

3. 配对求最大和：

   • 从中点开始遍历后半部分链表
   • 每次从栈中弹出一个值（这对应前半部分对称位置的节点值）
   • 将栈中弹出的值与当前后半部分节点的值相加
   • 更新最大和

代码实现二

publicintpairSum2(ListNodehead){// 快慢指针找到中间节点ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}// 遍历前半部分节点，将节点值加入栈中Deque<Integer>stack=newArrayDeque<>();while(head!=slow){stack.push(head.val);head=head.next;}// 遍历后半部分节点，弹出栈顶元素与当前节点值计算最大和intmaxSum=0;while(slow!=null){intfirstNum=stack.pop();intsecondNum=slow.val;maxSum=Math.max(maxSum,firstNum+secondNum);slow=slow.next;}returnmaxSum;}

复杂度分析

• 时间复杂度：O(n)，只需要遍历链表两次
• 空间复杂度：O(n/2)，只需要额外的空间存储前半部分节点的值
  优势：不需要修改原链表结构