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.
- may not alter the values in the list's nodes, only nodes itself may be changed.
给一个链表和正整数k，以每k个为一组来翻转链表。把原链表分成若干小段，然后分别对其进行翻转。
解法1：迭代
解法2: 递归
Java:
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
head = curr;
}
return head;
}
Python:
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next))
class Solution:
# @param head, a ListNode
# @param k, an integer
# @return a ListNode
def reverseKGroup(self, head, k):
dummy = ListNode(-1)
dummy.next = head
cur, cur_dummy = head, dummy
length = 0
while cur:
next_cur = cur.next
length = (length + 1) % k
if length == 0:
next_dummy = cur_dummy.next
self.reverse(cur_dummy, cur.next)
cur_dummy = next_dummy
cur = next_cur
return dummy.next
def reverse(self, begin, end):
first = begin.next
cur = first.next
while cur != end:
first.next = cur.next
cur.next = begin.next
begin.next = cur
cur = first.next
C++:
// Time: O(n)
// Space: O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy{0};
dummy.next = head;
auto curr = head, curr_dummy = &dummy;
int len = 0;
while (curr) {
auto next_curr = curr->next;
len = (len + 1) % k;
if (len == 0) {
auto next_dummy = curr_dummy->next;
reverse(&curr_dummy, curr->next);
curr_dummy = next_dummy;
}
curr = next_curr;
}
return dummy.next;
}
void reverse(ListNode **begin, const ListNode *end) {
ListNode *first = (*begin)->next;
ListNode *curr = first->next;
while (curr != end) {
first->next = curr->next;
curr->next = (*begin)->next;
(*begin)->next = curr;
curr = first->next;
}
}
};
C++:
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (!head || k == 1) return head;
ListNode *dummy = new ListNode(-1);
ListNode *pre = dummy, *cur = head;
dummy->next = head;
int i = 0;
while (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;
ListNode *cur = last->next;
while(cur != next) {
last->next = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = last->next;
}
return last;
}
};
C++:
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;
dummy->next = head;
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;
}
};
C++: 递归
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *cur = head;
for (int i = 0; i < k; ++i) {
if (!cur) return head;
cur = cur->next;
}
ListNode *new_head = reverse(head, cur);
head->next = reverseKGroup(cur, k);
return new_head;
}
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode *pre = tail;
while (head != tail) {
ListNode *t = head->next;
head->next = pre;
pre = head;
head = t;
}
return pre;
}
};
类似题目：
[LeetCode] 24. Swap Nodes in Pairs 成对交换节点