2130. Maximum Twin Sum of a Linked List

Problem Description

In this LeetCode problem, we are working with a linked list of even length n. The list has a special property: each node has a "twin," which is the node at the symmetric position from the other end of the list. For instance, in a list with n nodes, the 0-th node is the twin of the (n-1)-th node, and so on. The concept of twins only applies to the first half of the nodes in the list.

The "twin sum" is the sum of the value of a node and its twin's value. Our goal is to calculate and return the maximum twin sum that can be found in the given linked list.

To clarify with an example, if we have a linked list 1 -> 2 -> 3 -> 4, the twins are (1, 4) and (2, 3), leading to twin sums of 5 and 5. In this case, the maximum twin sum is 5.

Intuition

The challenge in this problem is to efficiently find the twin of each node so that we can calculate the twin sums. Since the list is singly linked, we cannot directly access the corresponding twin for a node in the first half of the list without traversing it.

An intuitive approach involves reversing the second half of the linked list so that we can then pair nodes from the first half and the reversed second half to calculate their sums. By iterating through the two halves simultaneously, we can easily calculate each twin sum and determine the maximum twin sum.

Here is the step-by-step thought process behind the solution:

1. Find the middle of the linked list. Since we have a fast and a slow pointer, where the fast pointer moves at twice the speed of the slow pointer, when the fast pointer reaches the end of the list, the slow pointer will be at the middle.

2. Once the middle is found, reverse the second half of the list starting from the node right after the middle node.

3. Two pointers can now walk through both halves of the list at the same time. Since the second half is reversed, the corresponding twins will be the nodes that these two pointers point to.

4. As we iterate, we calculate the sums of the twins and keep track of the maximum sum that we find.

5. Once we've traversed through both halves, the calculated maximum sum is returned as the result.

Learn more about Stack, Linked List and Two Pointers patterns.

Solution Approach

The given solution in Python implements the approach we've discussed. The main components of the solution involve finding the midpoint of the linked list, reversing the second half of the list, and then iterating to find the maximum twin sum. Here is how each step is accomplished:

1. Finding the Middle of the Linked List: Use the classic two-pointer technique known as the "tortoise and hare" algorithm. One pointer (slow) moves one node at a time, while the other (fast) moves two nodes at a time. When fast reaches the end of the list, slow will be at the midpoint.

   1slow, fast = head, head.next
   2while fast and fast.next:
   3    slow, fast = slow.next, fast.next.next

2. Reversing the Second Half: Once the midpoint is found, the solution defines a helper function reverse(head) to reverse the second half of the linked list starting from the node right after the middle (slow.next).

   1def reverse(head):
   2    dummy = ListNode()
   3    curr = head
   4    while curr:
   5        next = curr.next
   6        curr.next = dummy.next
   7        dummy.next = curr
   8        curr = next
   9    return dummy.next

   The reverse function makes use of a dummy node to easily reverse the linked list through pointer manipulation.

3. Calculating Maximum Twin Sum: After reversing the second half, we now have two pointers, pa that points at the head of the list and pb that points at the head of the reversed second half. We then iterate through the list using both pointers, which move in step with each other, calculating the sum of the values each points to and updating the ans variable if we find a larger sum.

   1pa = head
   2q = slow.next
   3slow.next = None  # Break the list into two halves
   4pb = reverse(q)
   5
   6ans = 0
   7while pa and pb:
   8    ans = max(ans, pa.val + pb.val)
   9    pa = pa.next
   10    pb = pb.next

4. Returning the Result: After the iteration, ans holds the maximum twin sum, which is then returned.

   1return ans

Overall, the solution iterates over the list twice: once to find the middle and once more to calculate the twin sum. This keeps the time complexity to O(n) where n is the number of nodes in the linked list. The space complexity is O(1) as it only uses a few extra pointers with no dependency on the size of the input list.

Example Walkthrough

To illustrate the solution approach, let's walk through a small example with the following linked list [1 -> 4 -> 2 -> 3].

1. Find the middle of the linked list: We start with two pointers, slow and fast. slow moves one step at a time, while fast moves two steps. We initialize them as slow = head and fast = head.next. In our example:

   • slow starts at 1 and fast starts at 4.
   • After the first step, slow is at 4, and fast is at 2.
   • After the second step, slow is at 2, and fast has reached the end None. At this point, we stop the iteration and slow is at the midpoint of the list.

2. Reverse the second half: We reverse the list starting from the node right after the middle (slow.next), so we reverse the list from 3 onwards. The list is small, so after reversing, the second half would just be [3 -> 2]. We would have:

   Original list: 1 -> 4 -> 2 -> 3
   After reversing: 1 -> 4 -> 3 -> 2

3. Calculating Maximum Twin Sum: We initialize two pointers, pa at the head of the list (1) and pb at the head of the reversed second half (3). Iterating through both halves simultaneously:

   • On the first calculation, pa.val is 1, and pb.val is 3. The sum is 4.
   • Move pa to the next node (4) and pb to its next node (2).
   • On the second calculation, pa.val is 4, and pb.val is 2. The sum is 6.
   • We track the maximum sum found, which is 6 after this iteration.

4. Returning the Result: With the iterations complete and no more nodes to traverse, we found that the maximum twin sum in our example linked list [1 -> 4 -> 2 -> 3] is 6. We return this value as the final result.

Solution Implementation

Time and Space Complexity

The given Python code defines a function to find the maximum twin sum in a singly-linked list, where the twin sum is defined as the sum of values from nodes that are equidistant from the start and end of the list.

Time Complexity

1. Reversing the second half of the linked list: The reverse function iterates over the nodes of the second half of the original linked list once, with a time complexity of O(n/2), where n is the total number of nodes in the list, because it stops at the midpoint of the list due to the previous pointer manipulation.

2. Finding the midpoint of the linked list: This is achieved by the "tortoise and hare" technique, where we move a slow pointer by one step and a fast pointer by two steps. When the fast pointer reaches the end, the slow pointer will be at the midpoint, and this has a time complexity of O(n/2) since the fast pointer traverses the list twice as fast as the slow pointer.

3. Calculating the maximum twin sum: This involves a single pass through the first half of the list while simultaneously traversing the reversed second half of the list, yielding a time complexity of O(n/2).

Adding these together gives 2 * O(n/2) + O(n/2), simplifying to O(n) as constants are dropped and n/2 is ultimately proportional to n.

Space Complexity

1. Additional space for reversing: The reverse function uses a constant amount of extra space, as it just rearranges the pointers without allocating any new list nodes.

2. Space for pointers: A few extra pointers are used for traversal and reversing the linked list (dummy, curr, slow, fast, pa, pb), which use a constant amount of space.

Therefore, the space complexity of the provided code is O(1) since it does not grow with the size of the input list and only a fixed amount of extra memory is utilized.

Learn more about how to find time and space complexity quickly using problem constraints.