Keshawn_lu's Blog

Leetcode 25. K 个一组翻转链表

字数统计: 542阅读时长: 2 min
2020/05/16 Share

题目简介:

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5

k = 2 时,应当返回: 2->1->4->3->5

k = 3 时,应当返回: 3->2->1->4->5

说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

思路:

首先设置一个翻转链表的函数,能将翻转后的头和尾传递出来。为了保存起始的头结点,设置一个结点指向起始的头结点。

将链表分为 k 个一组,head指向每组的头结点,若该分组长度大于等于 k ,则翻转该部分链表。在翻转时,还需要当前head的前一个结点pre,从而可以使翻转后的子链表的头部再接回pre,并需要每次子链表尾部的下一个结点nextnode,使翻转后的子链表的尾部接回nextnode

代码如下:

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
56
57
58
59
60
61
62
63
64
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

//翻转链表,返回新的链头和链尾
pair<ListNode*, ListNode*> ReverseLink(ListNode* head, ListNode* tail){

ListNode* pre = tail -> next;
ListNode* now = head;

while(pre != tail){

ListNode* nextnode = now -> next;
now -> next = pre;
pre = now;
now = nextnode;
}

return {tail, head};
}

ListNode* reverseKGroup(ListNode* head, int k) {

ListNode* hair = new ListNode(0);
hair -> next = head; //保存头结点

ListNode* pre = hair;

while(head){

ListNode* tail = pre;

for(int i = 0; i < k; i++){

tail = tail -> next;
if(!tail) //分组长度小于k
return hair -> next; //直接返回保存的头结点
}

ListNode* nextnode = tail -> next;
//翻转子链表
pair<ListNode*, ListNode*> res = ReverseLink(head, tail);
head = res.first;
tail = res.second;

pre -> next = head;
tail -> next = nextnode;
head = tail -> next;
pre = tail; //pre指向新head的前一个结点

}

return hair -> next;

}

};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: