Medium

题目描述

在一个长度为 n 的链表中，其中 n 是偶数，链表的第 i 个节点（下标从 0 开始）被称为第 (n-1-i) 个节点的 孪生节点，如果 0 <= i <= (n / 2) - 1。

例如，如果 n = 4，那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这些是 n = 4 时仅有的孪生节点。

孪生和 定义为一个节点和它孪生节点的值的和。

给你一个长度为偶数的链表的头节点 head，请你返回链表的 最大孪生和。

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和 1 分别是节点 3 和 2 的孪生节点。所有的孪生和都是 6。
链表中没有其他孪生节点。
因此，链表的最大孪生和是 6。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中存在孪生节点的节点有：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4
因此，最大孪生和为 max(7, 4) = 7。

示例 3：

输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001。

提示：

  • 链表的节点数目是 [2, 10^5] 范围内的偶数
  • 1 <= Node.val <= 10^5

解题思路

这道题要求找到链表中孪生节点的最大和。根据定义，第 i 个节点的孪生节点是第 (n-1-i) 个节点，也就是说前半部分的节点和后半部分对应位置的节点互为孪生。

思路分析

有几种解法：

解法一：数组存储（简单直观）

  • 遍历链表，将所有节点值存入数组
  • 使用双指针从数组两端向中间移动，计算孪生和
  • 时间复杂度 O(n)，空间复杂度 O(n)

解法二：反转后半部分链表（推荐）

  • 使用快慢指针找到链表中点
  • 反转后半部分链表
  • 同时遍历前半部分和反转后的后半部分，计算孪生和
  • 时间复杂度 O(n)，空间复杂度 O(1)

解法三：栈辅助

  • 遍历链表，将所有节点值压入栈
  • 再次遍历前半部分，每次弹出栈顶元素计算孪生和
  • 时间复杂度 O(n)，空间复杂度 O(n)

考虑到空间效率，推荐使用解法二。这种方法巧妙地利用链表反转，使得我们可以同时从两个方向遍历链表，而无需额外的存储空间。

代码实现

class Solution {
public:
    int pairSum(ListNode* head) {
        // 找到链表中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        // 计算最大孪生和
        int maxSum = 0;
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            maxSum = max(maxSum, first->val + second->val);
            first = first->next;
            second = second->next;
        }
        
        return maxSum;
    }
};

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # 找到链表中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 反转后半部分
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # 计算最大孪生和
        max_sum = 0
        first = head
        second = prev
        while second:
            max_sum = max(max_sum, first.val + second.val)
            first = first.next
            second = second.next
        
        return max_sum

public class Solution {
    public int PairSum(ListNode head) {
        // 找到链表中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 反转后半部分
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 计算最大孪生和
        int maxSum = 0;
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            maxSum = Math.Max(maxSum, first.val + second.val);
            first = first.next;
            second = second.next;
        }
        
        return maxSum;
    }
}

var pairSum = function(head) {
    // 找到链表中点
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 反转后半部分
    let prev = null;
    let curr = slow;
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // 计算最大孪生和
    let maxSum = 0;
    let first = head;
    let second = prev;
    while (second) {
        maxSum = Math.max(maxSum, first.val + second.val);
        first = first.next;
        second = second.next;
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
反转后半部分链表O(n)O(1)
数组存储O(n)O(n)
栈辅助O(n)O(n)

其中 n 是链表的长度。推荐使用反转后半部分链表的方法，既保证了时间效率，又实现了常数空间复杂度。

相关题目