2130. Maximum Twin Sum of a Linked List

發表於 | 分類於

problem

solution

option 1 - recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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:
    ListNode *left ;
    int maxTwinSum;
    void traverse(ListNode *right){
        if(!right) return;
        // postorder
        traverse(right->next);
        
        maxTwinSum = max(maxTwinSum, left->val + right->val);
        left = left->next;
        
    }
    int pairSum(ListNode* head) {
        // must be even length
        // Palindrome
        
        // init.
        left = head;
        maxTwinSum =0;
        traverse(head);
        return maxTwinSum;
    }
};

option 2 - iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int pairSum(ListNode* head) {
        stack<int> sta;
        ListNode *slow = head, *fast = head;
        while(fast && fast->next ){
            fast = fast->next->next;
            slow =slow->next;
        }
        fast = slow;
        int ret =0;
        while(slow){ sta.push(slow->val); slow=slow->next;}
        
        while(head!=fast){
            ret = max(sta.top()+ head->val , ret);
            head = head->next;
            sta.pop();
        }
        return ret;
    }
};

analysis

  • time complexity O(n)
  • sparse complexity O(n)