2130. Maximum Twin Sum of a Linked List

Time: O(n)

Space: O(1)

Intuition

Twin pairs are symmetric positions from the ends of the list: first with last, second with second-last, and so on. Finding every twin by indexing from both ends would need extra space or repeated traversals. Instead, locate the start of the second half with slow/fast pointers, reverse that half in place, and walk both halves together to evaluate each twin sum.

Algorithm

1Advance slow one step and fast two steps until fast reaches the end; slow then starts the second half.
2Reverse the linked list beginning at slow and keep the new head as tail.
3Initialize answer = 0.
4While tail is not null, update answer with max(answer, head.val + tail.val).
5Move head and tail one node forward each iteration.
6Return answer.

Example Walkthrough

Input: head = [5, 4, 2, 1]

1.Slow/fast split places slow at node 2, the start of the second half.
2.Reverse the second half: 2 -> 1 becomes 1 -> 2.
3.Compare twins: 5 + 1 = 6 and 4 + 2 = 6.
4.Maximum twin sum is 6.

Output: 6

Common Pitfalls

•Reverse only the second half, not the entire list.
•After reversal, head still points to the original first node of the first half.
•The loop should continue until tail becomes null, covering all twin pairs.

2130.cs

// Approach: Find the middle with slow/fast pointers, reverse the second half, then compare
// twin sums from both ends moving inward and track the maximum.
// Time: O(n) Space: O(1)

// Definition for singly-linked list.
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public 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;
    }
}

Was this solution helpful?