leetcode

commit ee2999fecc3f915e0758a7968618e0a644077092
parent fe4449f6bf1eb1a7e5e668705a033fb0743c4eee
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 14 Jun 2026 09:51:42 -0600

2130. maximum twim sum of a linked list

Diffstat:
M
max_twin_sum_list.c
 | 
60
+++++++++++++++++++++++++++++++++++++++++++++---------------
A
max_twin_sum_list.py
 | 
38
++++++++++++++++++++++++++++++++++++++

2 files changed, 83 insertions(+), 15 deletions(-)
diff --git a/max_twin_sum_list.c b/max_twin_sum_list.c
@@ -1,5 +1,5 @@
 // 2130. Maximum Twin Sum of a Linked List
-#include <stdlib.h>
+#include "leetcode.h"
 
 /*
  * in a linked-list of size 'n', where 'n' is even, the i'th node (0-indexed) of
@@ -9,24 +9,54 @@
  * = 4'. the twin sum is defined as the sum of a node and its twin. given the
  * 'head' of a linked list with even length, return the maximum twin sum of the
  * linked list.
- *
  */
 
-struct ListNode {
-  int val;
-  struct ListNode *next;
-};
+struct ListNode *reverse(struct ListNode *head) {
+  struct ListNode *prev = NULL;
+  while (head) {
+    struct ListNode *next = head->next;
+    head->next = prev;
+    prev = head;
+    head = next;
+  }
+  return prev;
+}
 
 int pairSum(struct ListNode *head) {
-  int arr[100001], i = 0, j;
-  while (head) {
-    arr[i++] = head->val;
+  struct ListNode *slow = head;
+  struct ListNode *fast = head;
+  while (fast->next->next) {
+    slow = slow->next;
+    fast = fast->next->next;
+  }
+  struct ListNode *half_head = reverse(slow->next);
+  int ans = 0;
+  while (half_head) {
+    int curr = head->val + half_head->val;
+    ans = fmax(ans, curr);
     head = head->next;
+    half_head = half_head->next;
   }
-  i--;
-  int max = -1;
-  for (int j = 0; j <= i / 2; j++)
-    if (arr[j] + arr[i - j] > max)
-      max = arr[j] + arr[i - j];
-  return max;
+  return ans;
+}
+
+int main() {
+  int h1i[] = {5, 4, 2, 1};
+  int h2i[] = {4, 2, 2, 3};
+  int h3i[] = {1, 100000};
+  struct ListNode *h1 = listnode_build(h1i, ARRAY_SIZE(h1i));
+  struct ListNode *h2 = listnode_build(h2i, ARRAY_SIZE(h2i));
+  struct ListNode *h3 = listnode_build(h3i, ARRAY_SIZE(h3i));
+  int r1 = pairSum(h1);
+  int r2 = pairSum(h2);
+  int r3 = pairSum(h3);
+  printf("%d\n", r1);
+  assert(r1 == 6);
+  printf("%d\n", r2);
+  assert(r2 == 7);
+  printf("%d\n", r3);
+  assert(r3 == 100001);
+  listnode_free(h1);
+  listnode_free(h2);
+  listnode_free(h3);
 }
diff --git a/max_twin_sum_list.py b/max_twin_sum_list.py
@@ -0,0 +1,38 @@
+# 2130. Maximum Twin Sum of a Linked List
+from leetcode import ListNode, listnode_build
+
+"""
+in a linked-list of size 'n', where 'n' is even, the i'th node (0-indexed) of
+the linked list is known as the twin of the 'n - 1 - i' node, if 0 <= i <= (n
+/ 2) - 1. for example, if 'n = 4', then node 0 is the twin of node 3, and
+node 1 is the twin node of node 2. these are the only nodes with twins for 'n
+= 4'. the twin sum is defined as the sum of a node and its twin. given the
+'head' of a linked list with even length, return the maximum twin sum of the
+linked list.
+"""
+
+
+class Solution:
+    def pairSum(self, head: Optional[ListNode]) -> int:
+        slow, fast, ans = head, head, 0
+        while fast and fast.next:
+            fast = fast.next.next
+            slow = slow.next
+        curr, prev = slow, None
+        while curr:
+            curr.next, prev, curr = prev, curr, curr.next
+        while prev:
+            ans = max(ans, head.val + prev.val)
+            prev = prev.next
+            head = head.next
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    h1 = listnode_build(vals=[5, 4, 2, 1])
+    h2 = listnode_build(vals=[4, 4, 2, 3])
+    h3 = listnode_build(vals=[1, 100000])
+    print(obj.pairSum(h1))
+    print(obj.pairSum(h2))
+    print(obj.pairSum(h3))