Description

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 1:

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.

 

Example 2:

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.

•  

Example 3:

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, 105].

• 1 <= Node.val <= 105

Thinking

To find the maximum pair, we have to compare them one by one, there is no shortcut here. As to how we get each pair, that's where we need to grind on. Of course we need to split it into two parts, the first half and the second half. Here are two methods:

• Store the first/second half, then compare them with two pointers.

• Reverse the first half, then traverse two halves with two pointers.

Store the first half approach

​x
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow = head, *fast = head;
        vector<int> firstHalf;
        while(fast->next && fast->next->next) {
            firstHalf.push_back(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }

        // Slow now pointing to the last node of the first half
        firstHalf.push_back(slow->val);
        slow = slow->next;
        
        auto iter = firstHalf.rbegin();
        int ans = 0;
        while(slow) {
            ans = max(ans, *iter + slow->val);
            slow = slow->next;
            iter += 1;
        }

        return ans;
    }
};

We first use slow-fast pointers to get the pointer that points to the middle of the list. In the process of doing slow-fast pointers, the slow pointer will traverse all the first half list, so we can use the slow pointer the get the first half values and store them in an array/vector. Then we can traverse the firstHalf array/vector with a reverse iterator and keep traverse the rest of the list with the slow pointer, comparing each sum and finally get the result.

Reverse the first half approach

xxxxxxxxxx
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow = head, *fast = head;
        ListNode dummy = ListNode(0);
        ListNode *prev = &dummy, *nxt = slow->next;

        while(fast->next && fast->next->next) {
            fast = fast->next->next;

            slow->next = prev;
            prev = slow;
            slow = nxt;
            nxt = slow->next;
        }

        // Slow now pointing to the last node of the first half
        ListNode *firstHalf = slow;
        slow->next = prev;
        slow = nxt;

        int ans = 0;
        while(slow) {
            ans = max(ans, firstHalf->val + slow->val);
            slow = slow->next;
            firstHalf = firstHalf->next;
        }

        return ans;
    }
};

To reverse the list, we at least need three pointers, the previous, the current and the next. Here we still reverse the first half list with the slow pointer and its corresponding previous and next pointers. After the reverse, we use firstHalf and the slow iterate simultaneously to get each pair.

What I learned

Got practiced of

• Fast-slow pointers

• LinkedList reverse