題目描述
給你一個鏈表，每 k 個節(jié)點一組進(jìn)行翻轉(zhuǎn)，請你返回翻轉(zhuǎn)后的鏈表码耐。
k是一個正整數(shù)，它的值小于或等于鏈表的長度溶其。
如果節(jié)點總數(shù)不是k的整數(shù)倍骚腥，那么請將最后剩余的節(jié)點保持原有順序。
說明：你的算法只能使用常數(shù)的額外空間瓶逃。
你不能只是單純的改變節(jié)點內(nèi)部的值束铭，而是需要實際進(jìn)行節(jié)點交換。
示例：
給你這個鏈表：1->2->3->4->5
當(dāng)k= 2 時厢绝，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng)k= 3 時契沫，應(yīng)當(dāng)返回: 3->2->1->4->5
題目解析
方法一：迭代法
解題思路
這個在上一題兩兩交換鏈表節(jié)點的基礎(chǔ)增加了難度怎披，需要K個一組進(jìn)行翻轉(zhuǎn)积担。首先我們可以將鏈表分為 “已翻轉(zhuǎn)”、“待翻轉(zhuǎn)”宫仗、“未翻轉(zhuǎn)” 三部分。在每次進(jìn)行翻轉(zhuǎn)前钞速，通過K值確定翻轉(zhuǎn)鏈表的范圍贷掖。
在上面一題已經(jīng)提到進(jìn)行鏈表翻轉(zhuǎn)時需要注意鏈表當(dāng)前遍歷節(jié)點嫡秕、其前驅(qū)節(jié)點和后繼節(jié)點渴语，需要額外的指針進(jìn)行標(biāo)識，防止鏈表翻轉(zhuǎn)后無法繼續(xù)向后遍歷昆咽。在這里我們 prev 指針代表待翻轉(zhuǎn)鏈表的前驅(qū)節(jié)點驾凶， end 指針代表待翻轉(zhuǎn)鏈表的末尾， next 指針代表待翻轉(zhuǎn)鏈表的后繼節(jié)點掷酗。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// 哨兵節(jié)點
ListNode dummy = new ListNode(0);
dummy.next = head;
// 待翻轉(zhuǎn)鏈表的前驅(qū)節(jié)點
ListNode prev = dummy;
// 待翻轉(zhuǎn)鏈表的結(jié)束位置
ListNode end = dummy;
while(end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
// 待翻轉(zhuǎn)鏈表的起始位置
ListNode start = prev.next;
// 待翻轉(zhuǎn)鏈表的后繼節(jié)點
ListNode next = end.next;
// 將待翻轉(zhuǎn)鏈表的next指針置為null调违，然后翻轉(zhuǎn)鏈表
end.next = null;
prev.next = reverse(start);
start.next = next;
// 前驅(qū)指針和結(jié)束指針移動
prev = start;
end = prev;
}
return dummy.next;
}
// 鏈表反轉(zhuǎn)
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
復(fù)雜度分析
時間復(fù)雜度：O(n*k)
空間復(fù)雜度：O(1)
方法二：遞歸法
解題思路
遞歸的思路主要在于將子問題傳遞到下一層遞歸函數(shù)處理，遞歸函數(shù)返回的即正確結(jié)果泻轰，當(dāng)前層只需要處理當(dāng)前層邏輯即可技肩。
當(dāng)前層只需要處理K個鏈表元素的翻轉(zhuǎn)，并調(diào)用遞歸函數(shù)處理后面未翻轉(zhuǎn)的鏈表浮声，遞歸函數(shù)處理完未翻轉(zhuǎn)鏈表后返回結(jié)果虚婿，當(dāng)前層拿到結(jié)果后與自身翻轉(zhuǎn)結(jié)束后的鏈表進(jìn)行拼接，最后得到完整的翻轉(zhuǎn)結(jié)果泳挥。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode reverseKGroup(ListNode head, int k) {
// terminator
if (head == null || head.next == null || k == 0) {
return head;
}
ListNode start = head , end = head;
for (int i = 0; i < k; i++) {
if (end == null) return head;
end = end.next;
}
// process data: reverse linked list
ListNode newHead = reverse(start, end);
// recursion
start.next = reverseKGroup(end, k);
return newHead;
}
private ListNode reverse(ListNode start, ListNode end) {
ListNode pre = null, curr = start, next = start;
while (curr != end) {
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
復(fù)雜度分析
時間復(fù)雜度：O(n*k)
空間復(fù)雜度：O(n)
