leetcode_25題——Reverse Nodes in k-Group(チェーンテーブル)

Reverse Nodes in k-Group  
Total Accepted: 34390 Total Submissions: 134865 My Submissions
Question
 Solution 
 
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
 
Hide Tags
 
Linked List
Have you met this question in a real interview? 
Yes
 
     
この問題は1種の循環再帰の方法を採用してすることができて、毎回逆順序のk個のノード、それから後のに対して前のと同じで、だから再帰の方法を採用することができます

#include<iostream>

using namespace std;





struct ListNode {

	int val;

	ListNode *next;

	ListNode(int x) : val(x), next(NULL) {}

};



ListNode* reverseKGroup(ListNode* head, int k) {

	if(k<=1||head==NULL)

		return head;

	ListNode *ptr0=head;

	ListNode *ptr1=head;

	ListNode *head1=NULL;

	ListNode *ptr2=NULL;



	int N=k-1;

	int flag=0;

	while(N--)

	{

		ptr1=ptr1->next;

		if(ptr1==NULL)

		{

			flag=1;

			break;

		}

	}

	if(flag==1)

		return ptr0;

	ptr2=ptr1->next;

	

	ListNode *ptr3=ptr0->next;

	if(ptr3==ptr1)

	{

		ptr1->next=ptr0;

		ptr0->next=reverseKGroup(ptr2,k);

		return ptr1;

	}

	ListNode *ptr4=NULL;

	ptr0->next=reverseKGroup(ptr2,k);

	while(1)

	{

		ptr4=ptr3->next;

		ptr3->next=ptr0;

		if(ptr4==ptr1)

			break;

		else

		{

			ptr0=ptr3;

			ptr3=ptr4;

		}		

	}

	ptr1->next=ptr3;

	return ptr1;

}



int main()

{



}