文章目錄
- 題目
- 題目決議
- 解題思路
- 1.定義一個節點 prevHead，且next為 head
- 2. 回圈遍歷鏈表
- 3. 回圈內部代碼步驟
- 3.1 創建 一個 prevHead 的 替身變數 reverseHead，沒錯顧名思義 就是記錄反轉偶數長度組 頭節點的前驅節點，在定義一個 節點變數 reverseTail ，用來記錄 偶數長度組尾巴節點的位置，另外，我們知道 偶陣列的判斷條件，就是 節點個位 偶數，所以，我們還需要創建一個整形變數count 來記錄節點個數
- 下面重點了：我們要開始判斷 該 “分組” 中的節點個數是否為偶數，通過 count 來判斷，我們都都知道 count 初始值0，i 初始值1，零肯定是小于一的，那么肯定是能進入回圈（注意 偶數長度組可能不止一個，所以我們肯定是需要一個回圈的）
- 分析上圖回圈中的代碼
- 接下來就是 反轉方法 reverse 的實作
- 最后附上代碼
題目
?
題目決議
簡單來說：就是給你一個鏈表，將其分組，第一組 有 1 個 節點，第二組有兩個節點，第三組有三個節點，以此類推，直到剩余的節點，無法滿足下一次分組，
我們要做的就是將 這些組中，節點個數是偶數的，進行反轉，但不影響鏈表的鏈接，
?
解題思路
1.定義一個節點 prevHead，且next為 head
目的： 記錄交換 鏈表偶數長度組 頭節點 的 前驅節點，用于反轉后，接回鏈表，
前面的搞定了，后面還需要一個節點變數來記錄 鏈表偶數長度組 尾結點 的 后驅節點，用于反轉后，接回鏈表，
且 等于 head
?
2. 回圈遍歷鏈表
但與往常有些不同
用的for回圈，且回圈條件就是 變數flag 必須為 0，也就是 tail 不能為 null，接著往后看就知道了，
為什么要這么寫呢？因為 我們需要 下標來判斷 進行分組 和判斷該組是否為 偶陣列，如果是那么就進行反轉，
至于，為什么 i 初始值是1，是因為，我們都知道第一個分組，只有一個節點，肯定不是偶陣列，
后面，我會利用節點個數 與 i 的關系，來讓 prevHead 和 tail 進行移位，方便確定偶陣列的頭節點前驅 和 尾結點，
?
3. 回圈內部代碼步驟
3.1 創建 一個 prevHead 的 替身變數 reverseHead，沒錯顧名思義 就是記錄反轉偶數長度組 頭節點的前驅節點，在定義一個 節點變數 reverseTail ，用來記錄 偶數長度組尾巴節點的位置，另外，我們知道 偶陣列的判斷條件，就是 節點個位 偶數，所以，我們還需要創建一個整形變數count 來記錄節點個數
?
下面重點了：我們要開始判斷 該 “分組” 中的節點個數是否為偶數，通過 count 來判斷，我們都都知道 count 初始值0，i 初始值1，零肯定是小于一的，那么肯定是能進入回圈（注意 偶數長度組可能不止一個，所以我們肯定是需要一個回圈的）
在分析之前該代碼之前，該回圈條件可以提前講一下 tail != null 和 count < j 這兩個條件中tail != null 是為了防止 后續 “分組” 時，剩余節點不夠，
而 count < j 是用來分組的，后面分析的時候，你就知道哦了，
分析上圖回圈中的代碼
再來接著看，反轉函式的實作，（注意我們reverseHead 是 偶陣列的前一個節點）
注意 頭節點的前驅節點 與 該組的尾結點，都是在 prevHead 和 tail 移動前，記錄了當前組頭節點的前驅節點 和 該組的尾結點，所以，放心將該兩個值，交給 reverse ，
?
接下來就是 反轉方法 reverse 的實作
?
最后附上代碼
/**
* 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 ListNode reverseEvenLengthGroups(ListNode head) {
ListNode prevHead = new ListNode();
prevHead.next = head;
ListNode tail = head;
int flag = 0;
for(int i = 1; flag == 0;i++){
ListNode reverseHead = prevHead;
ListNode reverseTail = null;
int count = 0;
while(tail!=null && count < i){
reverseTail = tail;
prevHead = prevHead.next;
tail =tail.next;
count++;
if(tail == null){// 鏈表節點已分配完
flag = 1;
}
}
if(count % 2 == 0){
prevHead = reverse(reverseHead,reverseTail);
}
}
return head;// 因為第一組是只有一節點，不用反轉，也就是說 head 沒有改變，直接回傳就行了，
}
public ListNode reverse(ListNode prevHead,ListNode tail){
ListNode head = prevHead.next;
ListNode cur = head;
ListNode prev = tail.next;
while(prev != tail){
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
prevHead.next = tail;
return head;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/404134.html
標籤：其他
上一篇：GDB除錯-從入門實踐到原理