這是我參與11月更文挑戰的第7天，活動詳情檢視： 2021最後一次更文挑戰
題目描述
解題思路
- 首先判斷傳入的連結清單的長度是否小于K，如果小于K則傳回原連結清單。
- 如果傳入的連結清單的長度大于等于k，則繼續下面的判斷。
- 初始化兩個指針，prev和cur,prev指針初始的時候為null,cur初始的時候為head指針指向的位置。
- 核心循環：首先儲存目前指針的下一個指針，然後讓prev前進一個，讓cur前進一個，最後将cur指針指向的投入遞歸，所有遞歸結束的時候，傳回prev。
AC代碼
var reverseKGroup = function(head, k) {
// 首先判斷傳入的連結清單的長度是否小于k，如果小于k，則傳回原連結清單
let flag = 0;
let temp = head;
while (temp) {
temp = temp.next;
flag++;
}
if (flag < k) {
return head;
}
// 初始化指針
let prev = null;
let cur = head;
let n = k;
while (cur != null && n-- > 0) {
// 首先儲存後一個節點
let next = cur.next;
// cur指針的next域指向前一個節點
cur.next = prev;
prev = cur;
cur = next;
}
// 修改head指針的next域指向遞歸的傳回結果
head.next = reverseKGroup(cur,k);
return prev;
};
複制代碼 圖解核心思路
題目反思
- 關于連結清單反轉類題目，可能會用到三指針，我們要想到這一點。
- 指針反轉的時候，很重要的一步就是儲存後一個指針，防止這個指針丢失。
- 循環的時候，一定要搞清楚當循環結束的時候，每一個指針所在的位置，以及每一個指針的含義，隻有搞清楚這一點，才知道将哪一個指針投入遞歸，才明白遞歸傳回的結果的含義。
- 連結清單類的題目中，反轉各種連結清單是面試的常考題，這道題目指的我們反複揣摩。