# 25. Reverse Nodes in k-Group

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.

``````-1->1->2->3->4->5
|        |  |
pre      cur next

-1->3->2->1->4->5
|     |  |
cur   pre next
``````

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = head;
for (int i = 1; cur; ++i) {
if (i % k == 0) {
pre = reverseOneGroup(pre, cur->next);
cur = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
ListNode* reverseOneGroup(ListNode* pre, ListNode* next) {
ListNode *last = pre->next, *cur = last->next;
while(cur != next) {
last->next = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = last->next;
}
return last;
}
};
``````

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;
int num = 0;
while (cur = cur->next) ++num;
while (num >= k) {
cur = pre->next;
for (int i = 1; i < k; ++i) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
pre = cur;
num -= k;
}
return dummy->next;
}
};
``````

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
for (int i = 0; i < k; ++i) {
cur = cur->next;
}
}
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode *pre = tail;
}
return pre;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/25

Swap Nodes in Pairs

https://leetcode.com/problems/reverse-nodes-in-k-group/

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11435/C%2B%2B-Elegant-and-Small

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11457/20-line-iterative-C%2B%2B-solution

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea