题目描述
英文题目
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list’s nodes, only nodes itself may be changed.
中文题目
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解决方法
方法一
- 描述
对于给定链表1->2->3->4->5，一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node，那么我们加入dummy node后的链表变为-1->1->2->3->4->5，如果k为3的话，我们的目标是将1,2,3翻转一下，那么我们需要一些指针，pre和next分别指向要翻转的链表的前后的位置，然后翻转后pre的位置更新
- 源码
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
反转链表 1->2-3->4
@param head 不带头结点
@return 反转后的链表 4->3->2->1
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *cur = head;
struct ListNode *prev = NULL;
while(cur) {
struct ListNode *temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
return prev;
}
/**
k个一组翻转链表 1->2->3->4->5
@param head 不带头结点
@param k 几个节点 2
@return 翻转后的链表 2->1->4->3->5
*/
struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
struct ListNode *root = NULL;
struct ListNode *p = NULL;
while (head != NULL) {
struct ListNode *tempHead = head;
struct ListNode *tempP = NULL;
int count = 0;
bool isReverse = true;
while (count < k) {
if (head == NULL) {
isReverse = false;
break;
}
tempP = head;
head = head->next;
count++;
}
tempP->next = NULL;
if (isReverse) {
if (root == NULL) {
root = reverseList(tempHead);
p = tempHead;
}
else {
p->next = reverseList(tempHead);
p = tempHead;
}
}
else {
if (root == NULL) {
root = tempHead;
}
else {
p->next = tempHead;
}
}
}
return root;
}
/**
k个一组翻转链表测试
*/
void reverseKGroup_test()
{
SingleLinkListNode *head = single_link_list_create();
single_link_list_insert_tail(head, 1);
single_link_list_insert_tail(head, 2);
single_link_list_insert_tail(head, 3);
single_link_list_insert_tail(head, 4);
single_link_list_insert_tail(head, 5);
printf("========k个一组翻转链表测试========\n");
single_link_list_dump_head(head);
SingleLinkListNode *new = reverseKGroup(head->next, 2);
single_link_list_dump(new);
}