每日一題(LeetCode)----鏈表–鏈表最大孿生和

1.題目（2130. 鏈表最大孿生和）

• 在一個大小為 n 且 n 為 偶數(shù) 的鏈表中，對于 0 <= i <= (n / 2) - 1 的 i ，第 i 個節(jié)點（下標從 0 開始）的孿生節(jié)點為第 (n-1-i) 個節(jié)點 。

  • 比方說，n = 4 那么節(jié)點 0 是節(jié)點 3 的孿生節(jié)點，節(jié)點 1 是節(jié)點 2 的孿生節(jié)點。這是長度為 n = 4 的鏈表中所有的孿生節(jié)點。

  孿生和 定義為一個節(jié)點和它孿生節(jié)點兩者值之和。

  給你一個長度為偶數(shù)的鏈表的頭節(jié)點 head ，請你返回鏈表的 最大孿生和 。

  示例 1：

  

  輸入：head = [5,4,2,1]
  輸出：6
  解釋：
  節(jié)點 0 和節(jié)點 1 分別是節(jié)點 3 和 2 的孿生節(jié)點。孿生和都為 6 。
  鏈表中沒有其他孿生節(jié)點。
  所以，鏈表的最大孿生和是 6 。
  

  示例 2：

  

  輸入：head = [4,2,2,3]
  輸出：7
  解釋：
  鏈表中的孿生節(jié)點為：
  - 節(jié)點 0 是節(jié)點 3 的孿生節(jié)點，孿生和為 4 + 3 = 7 。
  - 節(jié)點 1 是節(jié)點 2 的孿生節(jié)點，孿生和為 2 + 2 = 4 。
  所以，最大孿生和為 max(7, 4) = 7 。
  

  示例 3：

  

  輸入：head = [1,100000]
  輸出：100001
  解釋：
  鏈表中只有一對孿生節(jié)點，孿生和為 1 + 100000 = 100001 。
  

  提示：

  • 鏈表的節(jié)點數(shù)目是 [2, 105] 中的 偶數(shù) 。
  • 1 <= Node.val <= 105

2.解題思路

思路一

將鏈表的后一半進行反轉(zhuǎn)，然后將鏈表的前一半和后一半進行相加，通過比較得到結(jié)果

1.找到鏈表的后一半的起始節(jié)點

我們先計算出整個鏈表的長度，然后用一個指針指向鏈表表頭，向后走整個鏈表的一半長度，得到鏈表后一半的表頭

2.進行反轉(zhuǎn)

通過頭，拿，斷這三個指針實現(xiàn)反轉(zhuǎn)

3.定義一個存結(jié)果的變量，將反轉(zhuǎn)后的后一半鏈表與原鏈表的前一半進行相加（這里思路一和思路二實現(xiàn)方式不一樣，但是都差不多），然后每求出一個值，就和存結(jié)果的變量進行比較，如果大于，就把存結(jié)果的變量進行更新，如果不大于，就不進行更新

思路二：思路二和思路一一樣就是實現(xiàn)的方法不同

1.找到鏈表的后一半的起始節(jié)點

我們使用快慢指針找出后一半部分的起始節(jié)點。我們用慢指針和快指針同時指向 頭節(jié)點，然后，我們每次將慢指針向后移動一個節(jié)點，同時快指針向后移動兩個節(jié)點。當 快指針指向空結(jié)點時，慢指針就剛好指向鏈表了后一半部分的首節(jié)點

2.進行反轉(zhuǎn)

通過頭，拿，斷這三個指針實現(xiàn)反轉(zhuǎn)

3.定義一個存結(jié)果的變量，將反轉(zhuǎn)后的后一半鏈表與原鏈表的前一半進行相加（這里思路一和思路二實現(xiàn)方式不一樣，但是都差不多），然后每求出一個值，就和存結(jié)果的變量進行比較，如果大于，就把存結(jié)果的變量進行更新，如果不大于，就不進行更新

3.寫出代碼

思路一的代碼

class Solution {
public:int pairSum(ListNode* head) {int length1=0;ListNode* Temp=head;while(Temp){length1++;Temp=Temp->next;}int length2=length1/2;int t=length2;Temp=head;while(t--){Temp=Temp->next;}ListNode* head2=NULL;ListNode* na=Temp;ListNode* duan=Temp->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;for(int i=0;i<length2;i++){res=max(head->val+head2->val,res);head=head->next;head2=head2->next;}return res;}
};

思路二的代碼

class Solution {
public:int pairSum(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast){slow=slow->next;fast=fast->next->next;}ListNode* head2=NULL;ListNode* na=slow;ListNode* duan=slow->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;while(head2){res=max(head->val+head2->val,res);head2=head2->next;head=head->next;}return res;}
};