Leetcode Link

This problem can be approached using the reverse linked list technique.
If you haven’t solved Leetcode 206 before, I recommend doing that first to get familiar with how to reverse a singly linked list.

Input: head = [4,2,2,3]
Output: 7

Since the twin sum is defined as summing the i-th node from the start with the i-th node from the end (for a list of even length), we can reverse the linked list to simulate accessing nodes from the back.

Original: [4, 2, 2, 3]
Reversed: [3, 2, 2, 4]

Then we can traverse both lists in order and compute the sum of each pair.
In this case, we compare:

4 + 3 = 7
2 + 2 = 4
2 + 2 = 4
3 + 4 = 7

So the maximum twin sum is 7.

Since we cannot directly clone a linked list in Java, we need to manually copy the list. Here’s the helper function I wrote to do that:

public ListNode copyList(ListNode head) {
    if (head == null) return null;

    ListNode newHead = new ListNode(head.val);
    ListNode currOld = head.next;
    ListNode currNew = newHead;

    while (currOld != null) {
        currNew.next = new ListNode(currOld.val);
        currNew = currNew.next;
        currOld = currOld.next;
    }

    return newHead;
}

We create two copies of the original linked list:

  • One in original order
  • One reversed

Then we iterate over both lists and calculate the twin sum at each step.

One optimization that can be made: since twin pairs are symmetric, we only need to iterate halfway through the list.
Alternatively, we can use a fast and slow pointer to find the midpoint of the original list, reverse only the second half, and calculate the twin sums that way (more space-efficient).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        ListNode tempNode = copyList(head);
        ListNode curr = copyList(head);
        ListNode rev = reverseNode(tempNode);
        int max = 0;
        while (curr != null && rev != null) {
            int temp = curr.val + rev.val;
            if (temp > max) {
                max = temp;
            }
            curr = curr.next;
            rev = rev.next;
        }
        return max;
    }

    public ListNode reverseNode(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode copyList(ListNode head) {
        if (head == null) return null;

        ListNode newHead = new ListNode(head.val);
        ListNode currOld = head.next;
        ListNode currNew = newHead;

        while (currOld != null) {
            currNew.next = new ListNode(currOld.val);
            currNew = currNew.next;
            currOld = currOld.next;
        }

        return newHead;
    }

}