[LeetCode] 2130. Maximum Twin Sum of a Linked List

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/

Maximum Twin Sum of a Linked List - LeetCode

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

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 the maximum twin sum of the linked list.

 

n개의 노드를 가진 연결 리스트가 있다. 0-인덱스 기준 i 번째 노드의 쌍둥이 노드는 n-1-i번째이다.

쌍둥이의 가장 큰 합을 구하시오.

 

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

 

 

풀이

연결 리스트를 순회하면서 배열에 넣고, 배열의 양 끝부터 두 수를 구해서 합을 구해 합을 비교하여 가장 큰 값을 리턴한다.

절반을 나눠서 포인터를 반대로 하는 방법도 있다.

 

코드(C++)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        int sum = 0;
        vector<int> node_val;
        ListNode* current = head;

        while(current != nullptr){
            node_val.push_back(current -> val);
            current = current -> next;
        }

        int n = node_val.size();

        for(int i = 0; i < n/2; i++){
            sum = max(sum, node_val[i] + node_val[n-1-i]);
        }

        return sum;
    }
};