Day84 | 灵神 | 快慢指针 链表最大孪生和

2130.链表最大孪生和

2130. 链表最大孪生和 - 力扣（LeetCode）

思路：

比昨天的还要简单，还是一样的思路，找中间节点然后反转链表然后相加

完整代码：

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
35
36
37
38
class Solution {
public:
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, *cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    int pairSum(ListNode* head) 
    {
        ListNode *mid=middleNode(head);
        ListNode *head2=reverseList(mid);
        int res=0;
        while(head2)
        {
            int x=head->val+head2->val;
            res=max(res,x);
            head=head->next;
            head2=head2->next;
        }
        return res;
    }
};