Open songyy5517 opened 1 month ago
Apprach: Reverse the first half of the linked list with Two Pointers
Complexity Analysis
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int pairSum(ListNode head) {
// Intuition: Two pointers. Find the middle node and reverse the back half part.
// 1. Exception handling
if (head == null)
return 0;
// 2. Define two pinters
ListNode slow = head, fast = head, pre = null;
// 3. Find the middle node & Reverse the first half part
while (fast != null){
fast = fast.next.next;
ListNode p_next = slow.next;
slow.next = pre;
pre = slow;
slow = p_next;
}
// 5. Calculate the max sum
int max = Integer.MIN_VALUE;
while (pre != null){
max = Math.max(max, pre.val + slow.val);
slow = slow.next;
pre = pre.next;
}
return max;
}
}
2024/5/28
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.
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:
Example 2:
Example 3:
Intuition Essentially, the problem need to match the symmetric nodes in the linked list. A simple idea is to put all the nodes to a stack and a queue respectively, and then always check the top elements. But this way would take up $O(N)$ space. Another idea is that we can use two pointers to reverse the first half part of the linked list, and then start from the middle, we can always get a pair of twin nodes when looping through the linked list, which only oocupies $O(1)$ space.