文章目錄
- 題目
- 解題思維
- 來看我怎么做！第一步：創建一個 傀儡頭節點
- 第二步： 再創建一個 傀儡頭接節點 的替身tail - 你可以理解為尾巴節點（也就是我們的逆序節點中的尾巴節點），
- 第三步： 為 逆序 k 個節點 做準備，逆序節點中的頭節點前驅，我們有prev 記錄著，但是 逆序節點中的尾巴節點 tail 的 next 值，我們還沒處理，所以，我們需要創建 ListNode 變數 來記錄 tail.next，方便逆序后，重新接入原鏈表中，
- 第四步：創建一個逆序 k 個節點 的 方法 myReverse,回傳值為 ListNode[] 陣列，將我們逆序后 “頭節點”和“尾結點”回傳，也方便我們將其接回原鏈表當中，因為我們記錄 逆序節點 中 “頭節點的前驅節點prev” 和 “尾巴節點的前驅節點tail”
- 第四步的執行程序
- 第五步： 將回傳來的 “頭節點” 和 “尾結點”，重新置換剛開指向位置，方便我們后續接入原鏈表中，
- 第五步：效果
- 第六步：將逆序后的節點 重新接入鏈表中
- 第七步： 為下一次，k個節點 逆序做準備
- 第八步： 將 逆序后的鏈表回傳
- 程式寫到這里，就寫完了！
- 最后附上程式
題目
?
解題思維
既然 題目要求：每 k 個 節點，進行，一次旋轉，那我就“截取” k 個節點，將其逆序后，拼接回原鏈表，
這就是我們的解題思維！
?
來看我怎么做！第一步：創建一個 傀儡頭節點
目的一： 這個可以作為 交換 “頭節點的前驅節點”
目的二：創建一個 傀儡節點的替身節點prev，方便下一次 做 替換k個節點的 “頭節點的前驅節點”
目的三： 原先的頭節點，就可以作為 逆序節點中的 “頭節點”，
?
第二步： 再創建一個 傀儡頭接節點 的替身tail - 你可以理解為尾巴節點（也就是我們的逆序節點中的尾巴節點），
?
第三步： 為 逆序 k 個節點 做準備，逆序節點中的頭節點前驅，我們有prev 記錄著，但是 逆序節點中的尾巴節點 tail 的 next 值，我們還沒處理，所以，我們需要創建 ListNode 變數 來記錄 tail.next，方便逆序后，重新接入原鏈表中，
?
第四步：創建一個逆序 k 個節點 的 方法 myReverse,回傳值為 ListNode[] 陣列，將我們逆序后 “頭節點”和“尾結點”回傳，也方便我們將其接回原鏈表當中，因為我們記錄 逆序節點 中 “頭節點的前驅節點prev” 和 “尾巴節點的前驅節點tail”
第四步的執行程序
?
第五步： 將回傳來的 “頭節點” 和 “尾結點”，重新置換剛開指向位置，方便我們后續接入原鏈表中，
第五步：效果
?
第六步：將逆序后的節點 重新接入鏈表中
?
第七步： 為下一次，k個節點 逆序做準備
?
第八步： 將 逆序后的鏈表回傳
?
程式寫到這里，就寫完了！
?
最后附上程式
/**
* 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 reverseKGroup(ListNode head, int k) {
ListNode newHead = new ListNode();// 新建一個傀儡頭節點
newHead.next = head;// 將原本的 頭節點 head 接入 新頭節點的next
ListNode prev = newHead;
while(head!=null){// 如果head為null，說明沒有節點需要逆序了
ListNode tail = prev;
// 判斷 傀儡節點后面的 節點個數 是否滿足 逆序節點個數的要求
for(int i = 0;i < k;i++){
tail = tail.next;
if(tail == null){
return newHead.next;
}
}
ListNode tailNext = tail.next;
ListNode[] reverse = myReverse(head,tail);
head = reverse[0];
tail = reverse[1];
prev.next = head;
tail.next = tailNext;
prev = tail;
head = tail.next;
}
return newHead.next;
}
public static ListNode[] myReverse(ListNode head,ListNode tail){
ListNode pre = tail.next;
ListNode p = head;
while(pre != tail){
ListNode pNext = p.next;
p.next = pre;
pre = p;
p = pNext;
}
return new ListNode[]{tail,head};
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/389136.html
標籤：java