LeetCode第25题之Reverse Nodes in k-Group

本文主要是介绍LeetCode第25题之Reverse Nodes in k-Group，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基本思想是对每k个节点采用头插法，时间复杂度为O（n）。
C++代码：

#include <vector>
#include <iostream>
using namespace std;/*** 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) {if (k<2 || NULL == head || NULL == head->next)return head;//res->next记录返回结果ListNode * res = new ListNode(-1);res->next = head;//last_tail记录上一次对k个节点进行操作后的最后一个节点ListNode * last_tail = res;while(1){//找t_head之后是否有k个节点int n = 0;//      ListNode *num_p = t_head;ListNode *num_p = last_tail->next;while(num_p && n != k){++n;num_p = num_p->next;}//如果n等于k，则num_p为下一组的首节点的指针//不足k个节点，返回结果if(n != k){ListNode * t = res->next;delete res;return t;}//n == kelse{//pre记录待插入节点的上一个节点ListNode *pre = last_tail->next;//cur记录当前待插入的节点ListNode *cur = pre->next;//此时num_p为以t_head开头的第k+1个节点//将当前待插入的节点插到last_tail的后面while (cur != num_p){pre->next = cur->next;cur->next = last_tail->next;last_tail->next = cur;//指针后移cur = pre->next;}//k个节点插入完毕后，更新last_tail到当前操作的k个节点的最后一个节点last_tail = pre;}}}};
int main()
{Solution s;ListNode *head, *p;head = NULL;for (int i=7;i>0;--i){p = new ListNode(i);p->next = head;head = p;}ListNode *res = s.reverseKGroup(head, 3);p = res;while(p){cout<<p->val<<'\t';p = p->next;}return 0;
}