推 jimmy888: 看到大家都會寫程式 我又想那個了 05/18 00:21
推 pandix: 大師 05/18 03:43
https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/
2130. Maximum Twin Sum of a Linked List
給你一個偶數數量的鏈結串列，返回最大的一對串列和，一對串列為串列對半切之後從
中心點分別往左和右有相同距離的Node。
Example 1:
https://assets.leetcode.com/uploads/2021/12/03/eg1drawio.png
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:
https://assets.leetcode.com/uploads/2021/12/03/eg3drawio.png
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.
思路：
1.一個指標每次走一步，一個每次走兩步，當快指標走完的時候慢指標會在中間，把
慢指標停留的值紀錄在一個List。
2.慢指標繼續一步一步往後走並和 List 的尾端元素開始往前相加，並更新最大值。
Java Code：
---------------------------------------------
class Solution {
public int pairSum(ListNode head) {
int max = 0;
List<Integer> list = new ArrayList<>();
ListNode slow = head;
ListNode fast = slow;
while (fast != null) {
list.add(slow.val);
slow = slow.next;
fast = fast.next.next;
}
int i = 1;
while (slow != null) {
max = Math.max(max, list.get(list.size() - i++) + slow.val);
slow = slow.next;
}
return max;
}
}
---------------------------------------------
不想工作
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1684340307.A.038.html