2130. 链表最大孪生和

🟠   🔖  栈 链表 双指针  🔗 力扣 LeetCode

题目

In a linked list of size n, where n is even , the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

• For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return themaximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]

Output: 6

Explanation:

Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.

There are no other nodes with twins in the linked list.

Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]

Output: 7

Explanation:

The nodes with twins present in this linked list are:

• Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
• Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.

Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]

Output: 100001

Explanation:

There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

• The number of nodes in the list is an even integer in the range [2, 10^5].
• 1 <= Node.val <= 10^5

题目大意

在一个大小为 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, 10^5] 中的 偶数 。
• 1 <= Node.val <= 10^5

解题思路

思路一：链表转数组

1. 链表转换为数组：

   • 为了便于处理和计算孪生和，可以将链表转换为一个数组，这样可以通过数组的下标直接访问链表的元素，并轻松计算两个节点的和。
   • 遍历链表并将每个节点的值保存到数组 arr 中，链表的顺序保持不变。

2. 计算孪生和：

   • 孪生和的计算方式是：假设数组的长度为 n，对于第 i 个元素，它的孪生节点是数组中位置为 n-1-i 的元素。每对孪生节点的和就是 arr[i] + arr[n-1-i]。
   • 从数组的两头开始遍历，计算每一对孪生节点的和，并更新最大孪生和。

3. 返回最大值：遍历所有孪生节点对，最终返回最大值。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的节点数，将链表转化为数组的时间复杂度是 O(n)，计算孪生和的时间复杂度是 O(n / 2)，即 O(n)。
• 空间复杂度：O(n)，额外使用了一个数组 arr 来存储链表的节点值。

思路二：反转链表

思路一使用了额外的空间来存储链表元素，如果不希望使用额外的空间，可以使用双指针法来优化空间复杂度，找到中间节点、反转后半部分链表并计算孪生和。

1. 寻找中间节点：使用快慢指针方法，快指针每次走两步，慢指针每次走一步，最终慢指针会到达链表的中间节点。

2. 反转后半部分链表：在找到中间节点后，将链表的后半部分反转，这样可以方便从前后节点开始同时遍历。

3. 计算孪生和：从反转后的链表的开头开始，和原链表的前半部分进行配对，计算每一对孪生节点的和，并更新最大值。

复杂度分析

• 时间复杂度：O(n)，反转链表的操作是线性时间复杂度 O(n)，遍历链表计算孪生和也是 O(n)。
• 空间复杂度：O(1)，只使用了常数空间来存储指针。

代码

链表转数组

/**
 * @param {ListNode} head
 * @return {number}
 */
var pairSum = function (head) {
	// 将链表转化为数组
	const arr = [];
	while (head) {
		arr.push(head.val);
		head = head.next;
	}

	// 计算最大孪生和
	let res = 0;
	for (let i = 0; i < arr.length / 2; i++) {
		res = Math.max(res, arr[i] + arr[arr.length - 1 - i]);
	}
	return res;
};

反转链表

/**
 * @param {ListNode} head
 * @return {number}
 */
var pairSum = function (head) {
	// 快慢指针找到链表中点
	let slow = head,
		fast = head;
	while (fast && fast.next) {
		fast = fast.next.next;
		slow = slow.next;
	}

	// 反转后半部分链表
	slow = reverse(slow);
	fast = head;

	// 计算最大孪生和
	let res = 0;
	while (slow) {
		res = Math.max(slow.val + fast.val, res);
		slow = slow.next;
		fast = fast.next;
	}
	return res;
};

function reverse(head) {
	let prev = null;
	let cur = head;
	while (cur) {
		let next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}

相关题目

题号	标题	题解	标签	难度	力扣
206	反转链表	[✓]	递归 链表	🟢	🀄️ 🔗
234	回文链表	[✓]	栈 递归 链表 1+	🟢	🀄️ 🔗
876	链表的中间结点	[✓]	链表 双指针	🟢	🀄️ 🔗