Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2130.html
2130. Maximum Twin Sum of a Linked List (Medium)
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 node0is the twin of node3, and node1is the twin of node2. These are the only nodes with twins forn = 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
Related Topics:
Linked List, Two Pointers, Stack
Similar Questions:
Solution 1.
-
/** * 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) { ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode pa = head; ListNode q = slow.next; slow.next = null; ListNode pb = reverse(q); int ans = 0; while (pa != null) { ans = Math.max(ans, pa.val + pb.val); pa = pa.next; pb = pb.next; } return ans; } private ListNode reverse(ListNode head) { ListNode dummy = new ListNode(); ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; } } -
/** * 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; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* pa = head; ListNode* q = slow->next; slow->next = nullptr; ListNode* pb = reverse(q); int ans = 0; while (pa) { ans = max(ans, pa->val + pb->val); pa = pa->next; pb = pb->next; } return ans; } ListNode* reverse(ListNode* head) { ListNode* dummy = new ListNode(); ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = dummy->next; dummy->next = curr; curr = next; } return dummy->next; } }; -
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def pairSum(self, head: Optional[ListNode]) -> int: def reverse(head): dummy = ListNode() curr = head while curr: next = curr.next curr.next = dummy.next dummy.next = curr curr = next return dummy.next slow, fast = head, head.next while fast and fast.next: slow, fast = slow.next, fast.next.next pa = head q = slow.next slow.next = None pb = reverse(q) ans = 0 while pa and pb: ans = max(ans, pa.val + pb.val) pa = pa.next pb = pb.next return ans -
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func pairSum(head *ListNode) int { reverse := func(head *ListNode) *ListNode { dummy := &ListNode{} curr := head for curr != nil { next := curr.Next curr.Next = dummy.Next dummy.Next = curr curr = next } return dummy.Next } slow, fast := head, head.Next for fast != nil && fast.Next != nil { slow, fast = slow.Next, fast.Next.Next } pa := head q := slow.Next slow.Next = nil pb := reverse(q) ans := 0 for pa != nil { ans = max(ans, pa.Val+pb.Val) pa = pa.Next pb = pb.Next } return ans } func max(a, b int) int { if a > b { return a } return b } -
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function pairSum(head: ListNode | null): number { let fast = head; let slow = head; while (fast) { fast = fast.next.next; slow = slow.next; } let prev = null; while (slow) { const next = slow.next; slow.next = prev; prev = slow; slow = next; } let left = head; let right = prev; let ans = 0; while (left && right) { ans = Math.max(ans, left.val + right.val); left = left.next; right = right.next; } return ans; } -
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 { let mut arr = Vec::new(); let mut node = &head; while node.is_some() { let t = node.as_ref().unwrap(); arr.push(t.val); node = &t.next; } let n = arr.len(); let mut ans = 0; for i in 0..n >> 1 { ans = ans.max(arr[i] + arr[n - 1 - i]); } ans } }