題目描述
25.K個一組翻轉鏈表
給你一個鏈表，每 k 個節點一組進行翻轉，請你回傳翻轉后的鏈表，
k是一個正整數，它的值小于或等于鏈表的長度，
如果節點總數不是k的整數倍，那么請將最后剩余的節點保持原有順序，
說明：你的演算法只能使用常數的額外空間，
你不能只是單純的改變節點內部的值，而是需要實際進行節點交換，
示例：
給你這個鏈表：1->2->3->4->5
當k= 2 時，應當回傳: 2->1->4->3->5
當k= 3 時，應當回傳: 3->2->1->4->5
題目決議
方法一：迭代法
解題思路
這個在上一題兩兩交換鏈表節點的基礎增加了難度，需要K個一組進行翻轉，首先我們可以將鏈表分為 “已翻轉”、“待翻轉”、“未翻轉” 三部分，在每次進行翻轉前，通過K值確定翻轉鏈表的范圍，
在上面一題已經提到進行鏈表翻轉時需要注意鏈表當前遍歷節點、其前驅節點和后繼節點，需要額外的指標進行標識，防止鏈表翻轉后無法繼續向后遍歷，在這里我們 prev 指標代表待翻轉鏈表的前驅節點， end 指標代表待翻轉鏈表的末尾， next 指標代表待翻轉鏈表的后繼節點，
代碼示例
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;
}
// 哨兵節點
ListNode dummy = new ListNode(0);
dummy.next = head;
// 待翻轉鏈表的前驅節點
ListNode prev = dummy;
// 待翻轉鏈表的結束位置
ListNode end = dummy;
while(end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
// 待翻轉鏈表的起始位置
ListNode start = prev.next;
// 待翻轉鏈表的后繼節點
ListNode next = end.next;
// 將待翻轉鏈表的next指標置為null，然后翻轉鏈表
end.next = null;
prev.next = reverse(start);
start.next = next;
// 前驅指標和結束指標移動
prev = start;
end = prev;
}
return dummy.next;
}
// 鏈表反轉
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;
}
復雜度分析
時間復雜度：O(n*k)
空間復雜度：O(1)
方法二：遞回法
解題思路
遞回的思路主要在于將子問題傳遞到下一層遞回函式處理，遞回函式回傳的即正確結果，當前層只需要處理當前層邏輯即可，
當前層只需要處理K個鏈表元素的翻轉，并呼叫遞回函式處理后面未翻轉的鏈表，遞回函式處理完未翻轉鏈表后回傳結果，當前層拿到結果后與自身翻轉結束后的鏈表進行拼接，最后得到完整的翻轉結果，
代碼示例
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;
}
復雜度分析
時間復雜度：O(n*k)
空間復雜度：O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65516.html
標籤：其他