CareerCup

node reverse(node head,int n)
  {
    if(head==null)
    return null;
     node p,q=null,temp=head;
     while(k--)
     {
        p=q;
        q=temp;
        temp=temp.next;
        q.next=p;
      }
     head.next=reverse(temp,k);
   return q;
}

use recursion . in each recursion revrese N nodes

node reverse(node head,int n)
{
if(head==null)
return null;
node p,q=null,temp=haed;
while(k--)
{
p=q;
q=temp;
temp=temp.next;
q.next=p;
}
head.next=reverse(temp,k);
return Q;
}

sorry to give formaating
use recursion . in each recursion revrese N nodes

node reverse(node head,int n)
{
if(head==null)
return null;
node p,q=null,temp=haed;

while(k--)
{
p=q;
q=temp;
temp=temp.next;
q.next=p;
}
head.next=reverse(temp,k);
return Q;
}

we are not allowed to allocate new nodes here.

How about this one without recursive method?

void reverseLinkedListbyInterval(NODE **head,int n)
{
NODE *curNode, *swapNode,*prevNode=NULL,*reverseList=NULL,*newHead=NULL,*tempNode;

curNode = *head;

int counter =n;
if (n >= 1)
{
while(curNode)
{
while (counter>0)
{
tempNode = curNode->pNext;
curNode->pNext = reverseList;
reverseList = curNode;
curNode = tempNode;
counter--;
}
counter=n;
if (newHead==NULL)
newHead=reverseList;
else
{
for(swapNode = newHead;swapNode->pNext;swapNode = swapNode->pNext);
swapNode->pNext = reverseList;
}
reverseList=NULL;
}
}
*head = newHead;
}

Another version of the same

//Reverse alternate nodes
NODE *reverseAlternateNodes(NODE *head, int number)
{

if(number < 2)
return head;
NODE *prevListTail = NULL, *curNode = head, *newHead = NULL;
while(curNode)
{
NODE *prevNode = NULL, *nextNode = NULL, *sub_list_tail = NULL, *sub_list_head = NULL;
int count = number;
while(curNode && count)
{
if(number == count)
sub_list_tail = curNode;
//swap the node
nextNode = curNode->pNext;
curNode->pNext = prevNode;
prevNode = curNode;
curNode = nextNode;
--count;
if(curNode == NULL)
sub_list_head = prevNode;
else if(count == 1)
sub_list_head = curNode;
}
if(prevListTail)
prevListTail->pNext = sub_list_head;
else
newHead = sub_list_head;

prevListTail = sub_list_tail;
}
return newHead;
}

void reverse ( struct node *first , int n )
{
struct node *cur, *temp;
int i, j;
cur = first;
while ( cur) {
temp = cur->prev;
cur->prev = cur->next;
cur->next = temp;
cur = cur->prev;
} while ( cur != NULL);
cur = first;
i = 0 ;
while ( cur) {
j = 0;
while ( j < i) {
cur = cur ->prev;
j++;
}
j = i + ( 2 *n) -1;
temp = cur;
while ( j > 0 ) {
temp = temp->prev;
j--;
}
if ( !temp)
break;
cur->next = temp;
temp->prev = cur;
}
cur = first;
for ( i = 1; i<n; i++)
cur = cur->prev;
first = cur;
first->prev = NULL;
}

R(k, n)
	r = NULL
	if(k && tn)
		tn = n->nx
		n->nx = r
		r=n
		n = tn
		k--
	return r
	
PR(n)
	if(n == NULL)
		return
	h = n
	r = R(n, k)
	h->n = PR(tn)
	return r

The code is nice. It seems to have a bug or constraint that the length of linklist n and the interval k must have a GCD bigger than 1. For example, I test n=10, k=3, the program has an error. I fix the code as the following:

LinkNode* linkedlist::Reverse_Interval(LinkNode* head, int n){
	if(!head) return NULL;
	LinkNode* p, *q=NULL, *temp=head;
	int k=n;
	while(k--){
		p=q;
		q=temp;
		temp=temp->next;
		if(!temp) break;
		q->next=p;
	}
	head->next=Reverse_Interval(temp,n);
	return q;
}

Input: {75 191 176 175 155 151 143 128 118 98}
Output: {176 191 75 151 155 175 118 128 143 98}
here n=10, k=3