介紹面試會出現的題型

題目連結: 2130. Maximum Twin Sum of a Linked List

題目描述:在一個長度為 n（n 為偶數）的鏈結串列中，第 i 個節點和第 (n-1-i) 個節點被稱為一對孿生節點 (twin)。請返回這個鏈結串列中最大的孿生和。

Input: head = [5,4,2,1]
Output: 6

Input: head = [4,2,2,3]
Output: 7

Python

解題思路:
這題有兩個做法:
1.轉換成陣列，遍歷一次Linked List儲存到陣列中，再利用雙指針去計算題目要求的答案。
2.快慢指針 + 反轉後半部分。

以下分享快慢指針+反轉後半部分的作法。

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow = head
        fast = head
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        pre = None
        re = slow
        while re:
            temp = re.next
            re.next = pre
            pre = re
            re = temp
            
        head1 = head
        head2 = pre
        ans = 0
        while head2:
            curr = head1.val + head2.val
            ans = max(ans,curr)
            head1 = head1.next
            head2 = head2.next
        return ans

演算法分析:

• 第一段while迴圈是利用快慢指針找出中間節點，以利後續反轉。
• 第二段while迴圈就是在做反轉後半部分。
• 第三段while迴圈計算當前的twin_ans，最後回傳最大值。

複雜度分析:

• 時間複雜度為 O(n)。

  1. 找中點需要遍歷前半部分，O(n/2)。
  2. 反轉後半部分需要遍歷後半部分，O(n/2)。
  3. 最後求和需要再次遍歷前半部分，O(n/2)。

• 空間複雜度： O(1) (整個算法都是在原地修改指針，只使用了 slow, fast, pre, re, temp 等固定數量的額外變數)。

有問題可以底下留言!
下回見!!