【题目】
给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,则翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6。
如果节点的数量是不k的倍数则最终留出节点应该保持原样,每K个一反转,不到k个不用反转。用程序实现。
------美团校招
来自LeetCode :Reverse Nodes in k-Group
【代码】
#include <iostream> #include <list> using namespace std; struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; // head不带头结点 // k 旋转个数 // 最后不满k个不用旋转 ListNode *ReverseKGroup(ListNode *head, int k) { // 容错处理 if(head == NULL || k < 2){ return head; } //添加头结点 ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *pre,*cur,*tail; pre = dummy; // 分组旋转的第一个节点即旋转后的尾节点 tail = head; // 当前节点 cur = head; int count = 0; // 统计节点个数 while(cur != NULL){ cur = cur->next; count++; } // 旋转次数 int rCount = count / k; // 分组旋转下标 int index = 0; // 旋转 while(rCount){ // 分组旋转 // k节点只需旋转k-1节点 index = k-1; while(index){ //先删除 cur = tail->next; tail->next = cur->next; //再插入 cur->next = pre->next; pre->next = cur; index--; }//while pre = tail; tail = tail->next; rCount--; }//while return dummy->next; } int main(){ int A[] = {1,2,3,4,5}; ListNode *head = new ListNode(0); head->next = NULL; ListNode *node; ListNode *pre = head; for(int i = 0;i < 5;i++){ node = new ListNode(A[i]); node->next = NULL; pre->next = node; pre = node; } head = ReverseKGroup(head->next,3); while(head != NULL){ cout<<head->val<<" "; head = head->next; } cout<<endl; return 0; }