Maximum Twin Sum of a Linked List LeetCode solution in C++

1
class Solution {
2
 public:
3
  ListNode *reverse(ListNode *head) {
4
    ListNode *prev = NULL, *curr = head, *nextstop;
5
    while (curr) {
6
      nextstop = curr->next;
7
      curr->next = prev;
8
      prev = curr;
9
      curr = nextstop;
10
    }
11
    return prev;
12
  }
13

14
  ListNode *findMiddleNode(ListNode *head) {
15
    ListNode *slowptr = head, *fastptr = head->next;
16
    while (fastptr && fastptr->next) {
17
      slowptr = slowptr->next;
18
      fastptr = fastptr->next->next;
19
    }
20
    return slowptr;
21
  }
22

23
  int pairSum(ListNode *head) {
24
    int ans = 0;
25

26
    ListNode *midNode = findMiddleNode(head);
27
    ListNode *head2 = reverse(midNode->next);
28

29
    midNode->next = NULL;
30

31
    ListNode *p1 = head, *p2 = head2;
32
    while (p1 && p2) {
33
      ans = max(ans, p1->val + p2->val);
34
      p1 = p1->next;
35
      p2 = p2->next;
36
    }
37

38
    midNode->next = reverse(head2);
39

40
    return ans;
41
  }
42
};