Maximum Twin Sum of A Linked List

2130. 链表最大孪生和

分析

遍历链表：
- 第一次遍历链表计算长度 n
- 在第一次遍历的同时，将前 n/2 个节点的值压入栈中
计算孪生和：
- 从第 n/2 个节点开始，第二次遍历链表
- 弹出栈顶元素，与当前节点值相加计算孪生和，更新最大值
返回结果：
- 遍历完成后，返回最大孪生和

时间复杂度

计算长度：遍历链表一次，时间复杂度为 O(n)
计算孪生和：再次遍历后半部分链表，时间复杂度为 O(n/2)

总体时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 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


class Solution
{
public:
    int pairSum(ListNode* head)
    {
        // 栈用于存储前半部分链表节点的值
        std::stack<int> stk;

        // 第一次遍历计算链表长度
        int len = 0;
        for (ListNode* p = head; p; p = p->next)
            ++len;

        // 第二次遍历，将前半部分节点值压入栈中
        ListNode* p = head;
        for (int i = 0; i < len / 2; ++i)
        {
            stk.push(p->val);
            p = p->next;
        }

        // 计算最大孪生和
        int res = 0;
        while (p)
        {
            // 弹出栈顶值，与当前节点值相加
            res = std::max(res, p->val + stk.top());
            stk.pop();
            p = p->next;
        }

        return res;
    }
};