链表最大孪生和
难度:
标签:
题目描述
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
- 比方说，
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, 105]中的 偶数 。 1 <= Node.val <= 105
代码结果
运行时间: 808 ms, 内存: 46.4 MB
/*
* 题目思路：
* 1. 使用流收集链表节点值到列表。
* 2. 计算并找出最大的孪生和。
*/
import java.util.*;
import java.util.stream.Collectors;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public int pairSum(ListNode head) {
// 使用流收集链表节点值
List<Integer> list = new ArrayList<>();
ListNode current = head;
while (current != null) {
list.add(current.val);
current = current.next;
}
int n = list.size();
// 计算最大孪生和
return IntStream.range(0, n / 2)
.map(i -> list.get(i) + list.get(n - 1 - i))
.max()
.orElse(0);
}
}解释
方法:
此题解通过使用快慢指针来找到链表的中点，然后将链表一分为二。接着，反转链表的后半部分，以便使得前半部分和反转后的后半部分的节点可以直接相加得到孪生和。通过遍历这两个部分的链表，计算所有可能的孪生和，并记录其中的最大值。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择使用快慢指针来找到链表的中点？有没有其他方法可以找到链表的中点？
▷🦆
在反转链表的后半部分时，有没有考虑到链表的节点数目只有两个的情况？这样的情况下代码的行为是怎样的？
▷🦆
反转链表后，原链表的结构改变了。是否有方法在不改变原链表结构的情况下解决这个问题？
▷🦆
在计算孪生和的过程中，你使用了两个指针p1和p2分别遍历前半部分和反转后的后半部分。这种方法是否保证了所有情况下都能正确计算出孪生和，尤其是在链表长度很大的情况下？
▷