本文介绍: 【代码】LeetCode //C – 2130. Maximum Twin Sum of a Linked List。

2130. Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the

i

t

h

i^{th}

ith node (0-indexed) of the linked list is known as the twin of the

(

n

1

i

)

t

h

(n-1-i)^{th}

(n1i)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 the maximum 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

    ,

    1

    0

    5

    ]

    [2, 10^5]

    [2,105].

  • 1

    <

    =

    N

    o

    d

    e

    .

    v

    a

    l

    <

    =

    1

    0

    5

    1 <= Node.val <= 10^5

    1<=Node.val<=105

From: LeetCode
Link: 2130. Maximum Twin Sum of a Linked List


Solution:

Ideas:
  1. Use the two-pointer technique to find the middle of the linked list.
  2. Reverse the second half of the list.
  3. Sum the values of the corresponding nodes from the start and reversed second half to find the maximum sum.
  4. Return the maximum sum found.
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int pairSum(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return 0;
    
    // Step 1: Find the middle of the linked list
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Step 2: Reverse the second half of the linked list
    struct ListNode *prev = NULL, *next = NULL;
    while (slow) {
        next = slow->next;
        slow->next = prev;
        prev = slow;
        slow = next;
    }
    
    // Step 3: Pairwise sum the values from the start and end to find the maximum sum
    int maxSum = 0;
    struct ListNode *start = head, *end = prev;
    while (end) {
        maxSum = maxSum > (start->val + end->val) ? maxSum : (start->val + end->val);
        start = start->next;
        end = end->next;
    }
    
    // Step 4: Return the maximum sum
    return maxSum;
}

原文地址:https://blog.csdn.net/navicheung/article/details/135543105

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_56740.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注