CareerCup

We can pick every n elements of the list, reverse it, and then link the tail of the previous part to the head of the current part. Note that the interviewer would probably want you to do it in-place.

This is my implementation in c++:

using namespace std;

struct node{
	node *next;
	int data;
};

void reverseList(int N, node * &head)
{
	node *prvTail = NULL;
	node *cur, *prv, *nxt, *ptr1 = head;
	while (1)
	{
		int cnt = 0;
		cur = ptr1;
		prv = NULL;

		for (cnt = 0; cnt < N && ptr1 != NULL; cnt++)
		{
			prv = ptr1;
			ptr1 = ptr1->next;
		}


		if (prvTail == NULL)
			head = (cnt<N ? cur:prv);
		else
			prvTail->next = (cnt<N ? cur:prv);
		
		if (cnt < N)
			break;

		prvTail = cur;

		
		while (cur != ptr1)
		{
			nxt = cur->next;
			cur->next = prv;
			prv = cur;
			cur = nxt;
		}
	}
}

Time complexity is O(n). Additional space used is O(1)

Client program to test validity:

void addToHead(node * &head, int val)
{
	node *cur = new node;
	cur->data = val;
	cur->next = head;
	head = cur;
}

void printList(node *head)
{
	node *cur = head;
	while (cur != NULL)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}

int main()
{
	int tmp, sz, n;
	while (cin >> sz >> n)
	{
		node *head = NULL;
		while (sz--)
		{
			cin >> tmp;
			addToHead(head, tmp);
		}
		printList(head);
		reverseList(n, head);
		printList(head);
	}
}

i will divide the int val = totalCount % n and so the iteration will go till the n * val

int val = totalCount % n;
Stack<int> s = new Stack<int>();
 for(int i = 1 ; i <= n * val ; n++
                         
{ if(i % n == 0)
        s.Push(num[i]);   
        while(s.Count() > 0 )
                 Console.WriteLine(s.Pop());           
   }else {
 s.Push(num[i];
}
//For rest of the numbers
for(int i = val * n + 1 ; i < totalLength ; i++)
           Console.writeLine(num[i]);

i attempted at an answer using javascript in the following:

var revn = function(data, node) {
  var rdata = [];
  while (node <= data.length) {
    for (var i = node-1; i >=0; i--) {
      rdata.push(data[i]);
    }
    data = data.slice(node, data.length);
  }
  return rdata.concat(data);
}

I tried in this way:
Step 1: Node linkHead = new Node()
Step 2: Store first Node of Every Nth Nodes
Step 3: Reverse the next N nodes
Step 4: link the tail of reverse list to linkHead
Step 5: Continue Step 2 - Step 4 until the list is traversed.

Complexity: O(n)

I have added my solution. Appreciate any suggestion or improvement.

private static Node reverseNNodes(Node head, int n)
{
    Node currentNode = head.Next;
    Node prev = null;
    Node temp = null;
    Node linkHead = new Node();
    Node currentHead = currentNode;
    Node nextLinkFirstNode = null;
    int count = 1;
    while (currentNode != null)
    {
        if (count % n == 1)
        {
            nextLinkFirstNode = currentNode;
        }
        temp = prev;
        prev = currentNode;
        currentNode = currentNode.Next;
        prev.Next = temp;

        if (count % n == 0)
        {
            if (linkHead.Next == null)
            {
                linkHead.Next = prev;
                prev = temp = null;
            }
            else
            {
                currentHead.Next = prev;
                currentHead = nextLinkFirstNode;
                prev = temp = null;
            }
        }
        count++;
    }
    if (prev != null)
        currentHead.Next = prev;
            
    return linkHead;
}

How about just rearrange (reverse) contents of N items at a time? No pointer changes.
last : begin()+N;
start: begin()
reversecontents(start, last)
...add the usual checks

In Haskell:

getSubLists :: Int -> [Int] -> ([[Int]],[Int])
getSubLists n xs 
    | (length xs) < n = ([],xs)
    | otherwise =  let (res,rmd) = getSubLists n (drop n xs)
                            in
                                 ((take n xs):res,rmd)

reverseList :: Int -> [Int] -> [Int]
reverseList n xs = 
    let (sub,rmd) = getSubLists n xs
        reversed = map reverse sub       
    in
        (concat reversed) ++ rmd

I have tried it in C++ using Stacks. It takes O(n) time.

#include <iostream>
using namespace std;

class stack
{ 
public:
	stack (int =0);
	~stack(); 
	
	void push (int);
	int pop();
	void display();
	
private:
    int *p;
	int top, length;	
};

stack::stack(int size)
{ 
top=-1;
length= size;
if (size==0)
p=0;
else p= new int[length];
}

stack::~stack ()
{ 
if(p!=0)
 delete []p;
} 

void stack::push(int elem)
{
    if(p == 0)                //If the stack size is zero, allow user to mention it at runtime
    {
        cout<<"Stack of zero size"<<endl;
        cout<<"Enter a size for stack : ";
        cin >> length;
        p=new int[length];
    }
    if(top==(length-1))     //If the top reaches to the maximum stack size
    {
        cout<<"\nCannot push "<<elem<<", Stack full"<<endl;
        return;
    }
    else
    {
        top++;
        p[top]=elem;
    }
}

int stack::pop()
{
    if(p==0 || top==-1)
    {
        cout<<"Stack empty!";
        return -1;
    }
    int ret=p[top];
    top--;
 
    return ret;
} 


struct node 
{
int data;
node *next;
};

class list 
{ public:
     list(); 
		
	  void insert(int n);
	  void reverse(int n);
	  void display();
  private:
      void reverse (node*head, int n) ;
	  node*head;  	     
} ;

list::list ()
{ head=NULL;
} 

void list::reverse(node*head, int n) 
{ 
bool flag= true; 
stack S1(20); 

node*p = head;
 for (int i=1; i<=n; i++)
 { if (p== NULL) {flag= false; break;} 
   S1.push (p->data);
   p= p-> next; 
 }

node*h= head;
if (flag== true)
{ 
for (int j=1; j<=n; j++)
 { h-> data = S1.pop(); 
   h= h-> next;
 }

reverse (p,n);
}
} 

void list:: reverse (int n)
{ reverse (head, n);
} 
 
void list::insert (int n)
{   
node*newnode= new node;
newnode-> data= n;

node*h = head;
node*temp= head;
head= newnode;
newnode->next= temp;
   
}  

void list:: display() 
{ node*h= head; 
while (h!=NULL)
{ cout<< h->data << " " ;
  h= h->next;
}
} 

int main()
{ list L1;
int x;
cout<< "Enter the linked list in reverse order (0 to terminate)" << endl;
while (1)
{ cin>> x;
if (x== 0) break;
L1. insert (x);
}
L1. display(); 
cout<< "Enter the order of reversal" << endl;
int n;
cin>> n;
L1.reverse(n);
L1.display();
cin.get();
cin.ignore();
}