Skip to content

2130. Maximum Twin Sum of a Linked List 👍

  • Time: $O(n)$
  • Space: $O(1)$
 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
class Solution {
 public:
  int pairSum(ListNode* head) {
    int ans = 0;
    ListNode* slow = head;
    ListNode* fast = head;

    // `slow` points to the start of the second half.
    while (fast != nullptr && fast->next != nullptr) {
      slow = slow->next;
      fast = fast->next->next;
    }

    // `tail` points to the end of the reversed second half.
    ListNode* tail = reverseList(slow);

    while (tail != nullptr) {
      ans = max(ans, head->val + tail->val);
      head = head->next;
      tail = tail->next;
    }

    return ans;
  }

 private:
  ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head != nullptr) {
      auto next = head->next;
      head->next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
};

 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
class Solution {
  public int pairSum(ListNode head) {
    int ans = 0;
    ListNode slow = head;
    ListNode fast = head;

    // `slow` points to the start of the second half.
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    // `tail` points to the end of the reversed second half.
    ListNode tail = reverseList(slow);

    while (tail != null) {
      ans = Math.max(ans, head.val + tail.val);
      head = head.next;
      tail = tail.next;
    }

    return ans;
  }

  private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
}

 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
class Solution:
  def pairSum(self, head: ListNode | None) -> int:
    def reverseList(head: ListNode) -> ListNode:
      prev = None
      while head:
        next = head.next
        head.next = prev
        prev = head
        head = next
      return prev

    ans = 0
    slow = head
    fast = head

    # `slow` points to the start of the second half.
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next

    # `tail` points to the end of the reversed second half.
    tail = reverseList(slow)

    while tail:
      ans = max(ans, head.val + tail.val)
      head = head.next
      tail = tail.next

    return ans