83 lines
2.4 KiB
Markdown
83 lines
2.4 KiB
Markdown
---
|
||
id: "20220209"
|
||
date: "2022/02/09 10:38:05"
|
||
title: "leetcode.Q25.k个一组翻转链表"
|
||
tags: ["java", "leetcode", "链表"]
|
||
categories:
|
||
- "算法"
|
||
- "leetcode刷题"
|
||
---
|
||
|
||
## 解析思路
|
||
|
||
leetcode 困难，题目描述[点击这里](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)。
|
||
|
||
本题属于链表翻转的进阶题，思路如下：
|
||
|
||
<!-- more -->
|
||
|
||
1. 添加一个虚拟节点头，方便编码编写
|
||
2. 遍历链表，当遍历到k个时，对这k个进行处理，处理过程如下：
|
||
1. 对这k个节点进行翻转
|
||
2. 翻转后处理头尾节点的关系，注意需要记录头节点、头节点之前的一个节点、尾节点和尾节点的下一节点共四个节点，细节看代码
|
||
3. 一轮处理完毕后继续遍历，当遍历到k个时继续第2步，直到结束遍历
|
||
|
||
## 代码
|
||
|
||
```java
|
||
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);
|
||
}
|
||
}
|
||
|
||
``` |