[LeetCode] 2130. Maximum Twin Sum of a Linked List (C++)

Maximum Twin Sum of a Linked List - LeetCode

문제는 head만 주어진 상태에서 어떻게 linked list의 길이를 알 수 있냐인 것 같습니다.

List의 길이를 알지 못하면 어떤 노드들이 twin이 되는지 알지 못하니까요.

풀이

• Slow: node를 1개씩 이동
• Fast: node를 2개씩 이동

위와 같이 변수를 두개사용하면 Fast가 끝에 도착했을 때까지 Slow를 이동시키면 Slow는 linked list 중간에 있게 됩니다.

이점을 활용해서 저는 Slow가 중간지점까지 이동하며 stack에 지나가는 값들을 저장해두고, 중간지점 이후에는 stack의 값을 하나씩 가져와 twin의 값을 계산했습니다.

Code

/**
 * 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) {}
 * };
 */

#include <stack>
class Solution {
public:
    int pairSum(ListNode* head) {
        int answer = -1;
        stack<int> s;
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next){
            s.push(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }
        while(slow){
            answer = max(answer, s.top()+slow->val);
            slow = slow->next;
            s.pop();
        }

        return answer;
    }
};

 

 

문제설명

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.

 

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, 105].
• 1 <= Node.val <= 105