K个一组反转链表的理解

首先是对于反转链表的实现reverser()函数。这个很简单,使用三个指针就能实现。

而这一题可以直接复用这个reverser()函数的代码。只要四个指针就能实现。

1
2
3
4
lastTail -> 已经反转了链表的尾部
newHead -> 需要进行反转链表的头部
tail -> 需要进行反转链表的尾部
nextHead -> 下一个需要反转链表的头部

首先我们生成一个dummy节点指向head。lastTail指向这个dummyNode。其他三个指针指向head;

接下来就是迭代的过程:

  1. 首先将tail指针指向我们需要反转的这段链表的尾部;
  2. 将nextHead节点指向下一段需要反转的链表头部,也就是tail的下一个结点;
  3. 反转newHead开头的链表,并将lastTail的指针指向反转之后的链表头部;
  4. 重置lastTail、newHead以及tail指针到nextHead位置。

K个一组反转链表

代码实现:

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
//206. 反转链表
ListNode* reverseList(ListNode* head) {
if(head == nullptr) return head;
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* next = head->next;
while(curr != nullptr){
curr->next = prev;
prev = curr;
curr = next;
if(next != nullptr) next = next->next;
}
return prev;
}

//25. K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {
//右移k个元素,使其next == nullptr ,复用reverseList函数
ListNode* dummyNode = new ListNode();
dummyNode->next = head;

ListNode* lastTail = dummyNode;
ListNode* newHead = head;
ListNode* tail = head;
ListNode* nextHead = head;
while(tail != nullptr){
int i = k;
while(--i){
tail = tail->next;
if(tail == nullptr){
lastTail->next = newHead;
return dummyNode->next;
}
}

nextHead = tail->next;
tail->next = nullptr;
lastTail->next = reverseList(newHead);

lastTail = newHead;
newHead = nextHead;
tail = nextHead;

}
return dummyNode->next;
}

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发布/删除 文章

创建文章

进入博客目录,在 /source/_posts 文件夹下直接建立一个.md文件

1
hexo new "文章的题目"

发布新文章

文章写好后,直接在git bash中执行以下命令即可直接发布文章

1
hexo d -g

删除文章就是直接在source/_posts 文件夹下删除对应的.md文件,然后运行hexo d -g;

  • Copyrights © 2015-2022 John Doe
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信