leetcode.Q25.k个一组翻转链表

解析思路

leetcode 困难,题目描述点击这里

本题属于链表翻转的进阶题,思路如下:

  1. 添加一个虚拟节点头,方便编码编写
  2. 遍历链表,当遍历到k个时,对这k个进行处理,处理过程如下:
    1. 对这k个节点进行翻转
    2. 翻转后处理头尾节点的关系,注意需要记录头节点、头节点之前的一个节点、尾节点和尾节点的下一节点共四个节点,细节看代码
  3. 一轮处理完毕后继续遍历,当遍历到k个时继续第2步,直到结束遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Q25 {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode res = new ListNode(), index = head;
res.next = head;
int count = 0;
//left:开始翻转节点的父节点
//right:结束翻转的节点
ListNode beforeL = res, l = beforeL.next, r, afterR;
while (index != null) {
if (++count == k) {
//进行翻转
r = index;
afterR = index.next;
reverse(l, count);
index = l;
//处理头尾节点关系
l.next = afterR;
beforeL.next = r;
//进行下一轮循环
beforeL = index;
l = index.next;
count = 0;
}
index = index.next;
}
return res.next;
}

/**
* 翻转start后的n个节点
*
* @param start
* @param n
*/
private void reverse(ListNode start, int n) {
//反转节点
ListNode prev = null;
for (int i = 0; i < n; i++) {
ListNode next = start.next;
start.next = prev;
prev = start;
start = next;
}
}

public static void main(String[] args) {
ListNode node = new ListNode(1);
node.next = new ListNode(2);
node.next.next = new ListNode(3);
node.next.next.next = new ListNode(4);
node.next.next.next.next = new ListNode(5);
new Q25().reverseKGroup(node, 3);
}
}

本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号