LeetCode算法题(Go语言实现)

LeetCode算法题(Go语言实现)_32

题目

在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。
比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的最大孪生和。

一、代码实现

func pairSum(head *ListNode) int {// 快慢指针找中点slow, fast := head, headfor fast.Next != nil && fast.Next.Next != nil {slow = slow.Nextfast = fast.Next.Next}// 反转后半部分链表（网页2、4、5）var prev *ListNodecurrent := slow.Nextslow.Next = nil // 断开前后半链表for current != nil {next := current.Nextcurrent.Next = prevprev = currentcurrent = next}// 计算最大孪生和（网页3、4）maxSum := 0p1, p2 := head, prevfor p1 != nil && p2 != nil {sum := p1.Val + p2.Valif sum > maxSum {maxSum = sum}p1 = p1.Nextp2 = p2.Next}return maxSum
}

二、算法分析

1. 核心思路

双指针分割：通过快慢指针将链表分为前后两半
链表反转：反转后半部分链表以实现对称访问
并行遍历：同时遍历前半段和反转后的后半段计算孪生和

2. 关键步骤

快慢指针定位中点：快指针走两步，慢指针走一步，最终慢指针指向前半段末尾
反转后半链表：采用经典三指针法反转链表，时间复杂度 O(n/2)
孪生和计算：通过双指针并行遍历，比较每个对称节点对的和值

3. 复杂度

指标	值	说明
时间复杂度	O(n)	遍历链表三次（分割、反转、求和）
空间复杂度	O(1)	仅使用固定数量的指针变量

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

最小偶长链表：输入链表[1,2] → 输出3（直接首尾相加）
全相同元素：输入链表[5,5,5,5] → 输出10（每对和均为10）
极值分布：输入链表[0,100000] → 输出100000（边界测试）

2. 多语言实现

# Python实现
class Solution:def pairSum(self, head: ListNode) -> int:# 快慢指针分割slow = fast = headwhile fast.next and fast.next.next:slow = slow.nextfast = fast.next.next# 反转后半部分prev, curr = None, slow.nextslow.next = Nonewhile curr:next_node = curr.nextcurr.next = prevprev, curr = curr, next_node# 计算最大值max_sum = 0p1, p2 = head, prevwhile p1 and p2:max_sum = max(max_sum, p1.val + p2.val)p1, p2 = p1.next, p2.nextreturn max_sum

// Java实现
class Solution {public int pairSum(ListNode head) {// 快慢指针定位中点ListNode slow = head, fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}// 反转后半链表ListNode prev = null, curr = slow.next;slow.next = null;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}// 遍历求最大值int maxSum = 0;ListNode p1 = head, p2 = prev;while (p1 != null && p2 != null) {maxSum = Math.max(maxSum, p1.val + p2.val);p1 = p1.next;p2 = p2.next;}return maxSum;}
}