[LeetCode 题解]: Reverse Nodes in K-Groups

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

前言

【LeetCode 题解】系列传送门： http://www.cnblogs.com/double-win/category/573499.html

1.题目描述

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For 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

2. 题意

给定一个链表，将链表按照顺序分成k元素的组，并将每个组中的元素倒置。

注意：当小组中的元素不满k个时，不进行倒置操作。

3. 思路

可以利用插入法进行链表倒置，采用递归方法。

（1）链表倒置，可以参考文章：

（2）将链表分成k元素小组。

设置一个指针pre，指向插入点。

当插入的元素满足k个后，进行递归。

例如：链表为 1->2->3->4->5 k=2

可以将小组分为 1->2 3->4 5

for i range from 1 to k

tmp <- head

#将tmp插入到pre之后

head = head->next

（3）递归

上述步骤完成时， head->val = 3,进入到下一次处理

（4）终止条件，剩余的组中元素不足k个，将该组直接返回，不做倒置。

4: 解法

class Solution {
public:
int getListLen(ListNode *head){
int len=0;
ListNode *tmp=head;
while(tmp){len++;tmp=tmp->next;}
return len;
}
ListNode *reverseKGroup(ListNode *head, int k) {
if(k<=1|| !head || !head->next) return head;
int len=getListLen(head);
if(len<k) return head; ListNode *pre=new ListNode(0);
ListNode *change=head; for(int j=1;j<=k;j++){
ListNode *tmp = change;
change = change->next;
tmp->next = pre->next;
pre->next=tmp;
}
head->next=reverseKGroup(change,k);
return pre->next;
}
};