Introduction

In this blog post, we will explore how to solve the LeetCode problem "2130" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 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

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Reverse the Second Half: Reverse the second half of the linked list.
• Calculate Twin Sums: Iterate through the first half and the reversed second half, calculating the twin sums.

• Find Maximum: Keep track of the maximum twin sum encountered.

• Runtime Complexity: O(n) & Storage Complexity: O(1)

Code

    # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def pairSum(head: ListNode) -> int:
    # 1. Find the middle of the linked list
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. Reverse the second half of the linked list
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # 3. Calculate the maximum twin sum
    max_sum = 0
    first_half = head
    second_half = prev  # prev is now the head of the reversed second half

    while second_half:
        current_sum = first_half.val + second_half.val
        max_sum = max(max_sum, current_sum)
        first_half = first_half.next
        second_half = second_half.next

    return max_sum