[LeetCode] Maximum Twin Sum of a Linked List

Problem: In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th 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 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.

Example:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6. 

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7. 

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

• The number of nodes in the list is an even integer in the range [2, 10^5].
• 1 <= Node.val <= 10^5

Approach: First approach which comes to mind is just to get to the middle node of the list, reverse the list from there and then using two pointers one from the head say first and one from the middle node say second, keep comparing the sum of the nodes till the second pointer is not null. In the end return the maximum of such sum.

The above approach will work but what if we can't modify the input list? We can obviously make a copy of the linked list and apply the above approach but this could be expensive the list nodes are heavy and will be more space intensive. 

We can also use stack here. We can initially push all the nodes into stack. Now again we will take two pointers where one starts from head say first and another starts from top of the stack say second. We will keep comparing the sum of these nodes till next of first is not second. In the end we can return the maximum of all these sums.

Implementation in C#:

By modifying the input list:

    public int PairSum(ListNode head)

    {

        if (head == null)

        {

            return 0;

        }

        ListNode mid = this.GetMidNode(head);

        ListNode reverseHead = this.ReverseList(mid);

        ListNode first = head, second = reverseHead;

        int maxSum = 0;

        while(second != null)

        {

            maxSum = Math.Max(maxSum, first.val + second.val);

            first = first.next;

            second = second.next;

        }

        return maxSum;

    }

    private ListNode GetMidNode(ListNode head)

    {

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    private ListNode ReverseList(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode prev = null, curr = head;

        while(curr != null)

        {

            ListNode next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

        return prev;

    }

Using stack:

    public int PairSum(ListNode head)

    {

        if (head == null)

        {

            return 0;

        }

        var stack= new Stack<ListNode>();

        this.PushNodesToStack(head, stack);

        int maxSum = 0;

        ListNode fwd = head, rev = stack.Pop();

        while (fwd.next != rev)

        {

            if (maxSum < fwd.val + rev.val)

            {

                maxSum = fwd.val + rev.val;

            }

            fwd = fwd.next;

            rev = stack.Pop();

        }

        if (maxSum < fwd.val + rev.val)

        {

            maxSum = fwd.val + rev.val;

        }

        return maxSum;

    }

    private void PushNodesToStack(ListNode head, Stack<ListNode> stack)

    {

        for (ListNode node = head; node != null; node = node.next)

        {

            stack.Push(node);

        }

    }

Complexity: O(n)