2130. Maximum Twin Sum of a Linked List
題目連結: 2130. Maximum Twin Sum of a Linked List
題意
給定一個必定為偶數個 node 的 linked list
找出每組 twin
的最大和,twin
的定義如下:
n
為節點總數,當i
滿足0 <= i <= (n / 2) - 1
- 第
i
個節點 (0-indexed) 和第(n-1-i)
個節點會是twin
- e.g.
[1, 2, 3, 4, 5, 6]
(1, 6)
、(2, 5)
、(3, 4)
為 twins
限制
- The number of nodes in the list is an even integer in the range
[2, 10^5]
. 1 <= Node.val <= 10^5
思考
- 由 twin 的定義可知,若要知道某個點的 twin,就必須先找到 linked list 的中點
- 用快慢指標找出中間
- 將右半的 node 用 stack 儲存,從左半邊的 head 開始遍歷,便可以得到每一對 twin 並找出最大值,此作法空間複雜度為
O(n)
- 若將右半的 list 進行反轉,視為兩條平行的 linked list,在同樣 index 的 node 便是一對 twin,可在空間
O(1)
下完成
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 {
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
auto node = head;
while (node) {
auto next = node->next;
node->next = prev;
prev = node;
node = next;
}
return prev;
}
public:
int pairSum(ListNode* head) {
auto fast = head;
auto slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
auto mid = reverse(slow);
int ans = 0;
while (mid) {
ans = max(ans, head->val + mid->val);
head = head->next;
mid = mid->next;
}
return ans;
}
};
時間與空間複雜度分析
- 時間複雜度:
透過快慢指標找中點的過程是 O(n),反轉鏈結串列也需要 O(n/2) ≈ O(n),最後再進行一次遍歷比較,因此整體仍為 O(n)。 - 空間複雜度:
若使用反轉右半部的方式,只需常數個指標來輔助操作,故額外空間需求為 O(1)。若使用 stack 儲存右半部節點則需 O(n) 空間。
Comments ()