Solution: Maximum Twin Sum of a Linked List
Let’s solve the Maximum Twin Sum of a Linked List problem using the Fast and Slow Pointers pattern.
We'll cover the following
Statement
In a linked list of even length
The twin sum is defined as the sum of a node’s value and its twin’s value.
Given the head of a linked list with an even number of nodes, return the maximum twin sum of the linked list.
Constraints:
The list contains an even number of nodes in the range
. Node.data
Solution
The main idea behind finding the maximum twin sum in a linked list is to reverse the second half of the list and sum the corresponding values from both halves. The algorithm first locates the middle node using fast and slow pointers to achieve this. Then, it reverses the second half of the linked list, starting from the middle node. After that, it calculates the twin sums by adding the values of the nodes from the start of the list and the reversed second half while keeping track of the maximum sum found so far. Finally, it returns the maximum sum encountered during the traversal.
Using the above intuition, the solution can be implemented as follows:
The first step is to find the middle node of the linked list:
Initialize two pointers,
slow
andfast
, at the head of the linked list. Theslow
pointer will move one node at a time, while thefast
pointer will move two nodes at a time.Iterate through the linked list using these pointers as long as the
fast
pointer and its next node are not NULL. Theslow
pointer moves one step, and thefast
pointer moves two steps. By the time thefast
pointer reaches the end, theslow
pointer will be in the middle of the list.
The next step is to reverse the second half of the linked list:
Start iterating the linked list from the middle by initializing a pointer,
curr
, at the node whereslow
points.Initialize another pointer
prev
with NULL.Continue the loop as long as the
curr
is not NULL.Inside the loop, modify the pointers as follows:
First, save
curr.next
totemp
for later use.Update
curr.next
toprev
.Update
prev
tocurr
.Update
curr
totemp
.
The final step is to find the twin sum for all twin nodes in the linked list:
First, initialize
maxSum
withto keep track of the maximum twin sum found so far. Initialize the
curr
pointer at the head of the linked list. Due to the reversing algorithm, theprev
pointer would already be pointing at the head of the reversed second half.Iterate through the list until
prev
reaches NULL.Find the twin sum inside the loop by adding the data of the
curr
node and theprev
node.If this sum is greater than
maxSum
, updatemaxSum
with this sum.Move both
prev
andcurr
pointers forward.
Finally, return
maxSum
as the maximum twin sum of the given linked list.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.