Description

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인 연결 리스트에서, n이 짝수일 때, 연결 리스트의 ith 노드(0-인덱스)는 (n-1-i)th 노드의 쌍둥이로 알려져 있습니다. 여기서 0 <= i <= (n / 2) - 1입니다.

• 예를 들어, 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

Solution

class Solution {
    public int pairSum(ListNode head) {
        Deque<Integer> values = new ArrayDeque<>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }

        int max = 0;
        while (values.size() != 0) {
            max = Math.max(max, values.removeFirst() + values.removeLast());
        }
        return max;
    }
}