Leetcode 2130: Maximum Twin Sum of a Linked List
You are given a linked list with an even number of nodes. Each node in the list has a twin located symmetrically from the center of the list. Specifically, the ith node is the twin of the (n-1-i)th node, where n is the total number of nodes in the list. For example, the first node is the twin of the last node, the second node is the twin of the second last node, and so on. The twin sum is defined as the sum of a node and its twin. Your task is to return the maximum twin sum of the linked list.
Problem
Approach
Steps
Complexity
Input: You are given the head of a singly linked list with an even number of nodes.
Example: head = [3, 1, 4, 2]
Constraints:
• The number of nodes in the list is even.
• 1 <= Node.val <= 10^5.
Output: Return the maximum twin sum, which is the largest sum of a node and its twin in the linked list.
Example: Input: head = [3, 1, 4, 2] Output: 6
Constraints:
• The solution should return a single integer representing the maximum twin sum.
Goal: The goal is to calculate the twin sum for all possible pairs of nodes and return the maximum sum.
Steps:
• 1. Use two pointers, slow and fast, to find the middle of the linked list.
• 2. Reverse the second half of the list starting from the slow pointer.
• 3. Calculate the twin sum by adding the corresponding nodes from the first and second halves.
• 4. Keep track of the maximum twin sum while traversing the two halves.
Goal: The solution must handle linked lists with even lengths and compute the twin sums efficiently.
Steps:
• The linked list contains an even number of nodes.
• The value of each node is between 1 and 10^5.
Assumptions:
• The list has at least two nodes.
• There is no need to handle odd-length lists.
• Input: Input: head = [3, 1, 4, 2]
• Explanation: In this case, the first node (3) and the last node (2) form a twin pair with a sum of 5. Similarly, the second node (1) and the third node (4) form another twin pair with a sum of 5. The maximum twin sum is 6.
• Input: Input: head = [5, 3, 7, 4]
• Explanation: The first node (5) and the last node (4) form a twin pair with a sum of 9. The second node (3) and the third node (7) form a twin pair with a sum of 10. Therefore, the maximum twin sum is 10.
Approach: The approach to solving this problem involves finding the middle of the linked list, reversing the second half, and then calculating the twin sums.
Observations:
• We need to reverse the second half of the linked list and calculate the twin sums with the first half.
• By using a slow and fast pointer approach, we can efficiently find the middle of the list, then reverse the second half and calculate the twin sums in a single pass.
Steps:
• 1. Initialize two pointers: slow and fast.
• 2. Move slow to the middle of the list while moving fast twice as fast as slow.
• 3. Reverse the second half of the list starting from slow.
• 4. Traverse both halves simultaneously and compute the twin sums.
• 5. Return the maximum twin sum.
Empty Inputs:
• This problem does not require handling for empty lists as it is guaranteed that the number of nodes is even and at least 2.
Large Inputs:
• Ensure that the solution can handle linked lists with a large number of nodes, up to the limit of 10^5 nodes.
Special Values:
• The value of each node can range from 1 to 10^5, so ensure that the sums are calculated correctly for large numbers.
Constraints:
• The solution must be efficient enough to handle large inputs within the time limits.
int pairSum(ListNode* head) {
ListNode* slow = head, *fast = head;
while(slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
/*
if its a even chain fast pointer will go out of index
slow will reach at second of middle elements or first of second half of the chain
*/
ListNode *cur = slow, *prv = NULL, *nxt;
while(cur) {
nxt = cur->next;
cur->next = prv;
prv = cur;
cur = nxt;
}
int res = 0;
while(prv) {
res = max(res, head->val + prv->val);
head = head->next;
prv = prv->next;
}
return res;
}
1 : Declaration
int pairSum(ListNode* head) {
Function declaration for pairSum, which takes the head of a linked list and returns an integer.
2 : Pointer Setup
ListNode* slow = head, *fast = head;
Two pointers (slow and fast) are initialized to the head of the linked list to find the middle.
3 : Loop Setup
while(slow && fast && fast->next) {
A while loop to move the slow pointer one step and the fast pointer two steps to find the middle of the list.
4 : Pointer Movement
slow = slow->next;
Move the slow pointer one step forward.
5 : Pointer Movement
fast = fast->next->next;
Move the fast pointer two steps forward.
6 : Reversal Initialization
ListNode *cur = slow, *prv = NULL, *nxt;
Initialize three pointers: cur to slow (start of second half), prv as NULL, and nxt to help in reversing the list.
7 : Loop Setup
while(cur) {
Start of a loop to reverse the second half of the linked list.
8 : Pointer Movement
nxt = cur->next;
Store the next node of cur to help in the reversal process.
9 : Pointer Update
cur->next = prv;
Reverse the pointer of the current node to point to the previous node.
10 : Pointer Movement
prv = cur;
Move the previous pointer to the current node.
11 : Pointer Movement
cur = nxt;
Move the current pointer to the next node.
12 : Result Initialization
int res = 0;
Initialize the result variable to 0, which will store the maximum pair sum.
13 : Loop Setup
while(prv) {
Start of a while loop to find the maximum pair sum.
14 : Max Calculation
res = max(res, head->val + prv->val);
Calculate the sum of the current nodes from both halves and update the result with the maximum value.
15 : Pointer Movement
head = head->next;
Move the head pointer to the next node in the first half of the list.
16 : Pointer Movement
prv = prv->next;
Move the prv pointer to the next node in the second half of the list.
17 : Return
return res;
Return the computed result, which is the maximum pair sum.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we traverse the list at most twice, where n is the number of nodes in the linked list.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we are only using a constant amount of extra space, aside from the input list itself.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus