⭐️⭐️
# 題目敘述
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 node0
is the twin of node3
, and node1
is the twin of node2
. These are the only nodes with twins forn = 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.
# Solution
/** | |
* 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) { | |
vector<int> left; | |
ListNode *slow = head, *fast = head->next; | |
left.push_back(slow->val); | |
while (fast->next && fast->next->next) { | |
slow = slow->next; | |
fast = fast->next->next; | |
left.push_back(slow->val); | |
} | |
slow = slow->next; | |
int res = 0; | |
reverse(left.begin(), left.end()); | |
for (int i=0; i<left.size(); i++) { | |
res = max(res, left[i] + slow->val); | |
slow = slow->next; | |
} | |
return res; | |
} | |
}; |
class Solution { | |
public int pairSum(ListNode head) { | |
Deque<Integer> dq = new LinkedList<>(); | |
ListNode curr = new ListNode(); | |
curr = head; | |
while(curr != null){ | |
dq.add(curr.val); | |
curr = curr.next; | |
} | |
int max = Integer.MIN_VALUE; | |
while(!dq.isEmpty() && dq.size() >= 2){ | |
max = Math.max(max, dq.pollFirst() + dq.pollLast()); | |
} | |
return max; | |
} | |
} |