攀溃客網(wǎng)高頻算法題系列-BM3-鏈表中的節(jié)點(diǎn)每k個(gè)一組翻轉(zhuǎn)
題目描述
將給出的鏈表中的節(jié)點(diǎn)每 k 個(gè)一組翻轉(zhuǎn)憨栽，返回翻轉(zhuǎn)后的鏈表如果鏈表中的節(jié)點(diǎn)數(shù)不是 k 的倍數(shù)帜矾，將最后剩下的節(jié)點(diǎn)保持原樣你不能更改節(jié)點(diǎn)中的值，只能更改節(jié)點(diǎn)本身屑柔。
原題目見(jiàn)：BM3 鏈表中的節(jié)點(diǎn)每k個(gè)一組翻轉(zhuǎn)
解法一：遞歸
使用遞歸的方式處理每k個(gè)一組的結(jié)點(diǎn)屡萤，具體處理方式如下：
- 首先用tail記錄每次翻轉(zhuǎn)的尾部，就是第k+1個(gè)結(jié)點(diǎn)掸宛，從頭結(jié)點(diǎn)開(kāi)始死陆，遍歷鏈表，找到第k+1個(gè)結(jié)點(diǎn)唧瘾，如果當(dāng)前結(jié)點(diǎn)數(shù)不夠k個(gè)措译，則不用反轉(zhuǎn)直接返回；
- 然后從鏈表頭開(kāi)始遍歷饰序，翻轉(zhuǎn)結(jié)點(diǎn)并記錄反轉(zhuǎn)后的表頭pre和表尾結(jié)點(diǎn)head领虹；
- 然后遞歸處理從tail開(kāi)始的后面的鏈表結(jié)點(diǎn)，并將head指向遞歸處理后的鏈表求豫；
- 返回新的表頭即為反轉(zhuǎn)后的新的鏈表的表頭結(jié)點(diǎn)塌衰。
代碼
public class Bm003 {
/**
* 遞歸
*
* @param head ListNode類
* @param k int整型
* @return ListNode類
*/
public static ListNode reverseKGroup(ListNode head, int k) {
// 找到每次翻轉(zhuǎn)的尾部
ListNode tail = head;
// 遍歷k次到尾部
for (int i = 0; i < k; i++) {
// 如果不足k到了鏈表尾部，直接返回蝠嘉，不翻轉(zhuǎn)
if (tail == null) {
return head;
}
tail = tail.next;
}
// 翻轉(zhuǎn)時(shí)需要的前序和當(dāng)前節(jié)點(diǎn)
ListNode pre = null, cur = head;
// 在到達(dá)當(dāng)前段尾部節(jié)點(diǎn)前
while (cur != tail) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// 當(dāng)前尾部指向下一段要翻轉(zhuǎn)的鏈表
head.next = reverseKGroup(tail, k);
return pre;
}
public static void main(String[] args) {
ListNode head = ListNode.testCase2();
System.out.println("翻轉(zhuǎn)之前");
ListNode.print(head);
// 當(dāng)k=2時(shí)
ListNode newHead = reverseKGroup(head, 2);
System.out.println("當(dāng)k=2時(shí)最疆，翻轉(zhuǎn)之后");
ListNode.print(newHead);
ListNode head1 = ListNode.testCase2();
// 當(dāng)k=3時(shí)
ListNode newHead2 = reverseKGroup(head1, 3);
System.out.println("當(dāng)k=3時(shí)，翻轉(zhuǎn)之后");
ListNode.print(newHead2);
}
}
相信堅(jiān)持的力量蚤告！
