## Global Scholar Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}Node, *PNode;
PNode Reverse_K(PNode head, int k)
{
int count;
PNode pcur, pnext, ppre;
PNode pfirst1 = NULL, pfirst2 = NULL;
PNode phead;
pnext = head;
int bfirst = 0;
int nextcount = 0; //use this variable to multiples of 2
while (pnext!=NULL)
{
ppre = NULL;
pcur = NULL;
if (nextcount%2 == 0)
{
pfirst1 = pnext;
}
else
pfirst2 = pnext;
count = 0;
while(count<k&&pnext!=NULL){ //k-Node's reverse
pcur = pnext;
pnext = pcur->next;
pcur->next = ppre;
ppre = pcur;
count++;
}
nextcount++;
if(bfirst==0) //mark the first head and return phead
{
phead = pcur;
bfirst = 1;
}
if (nextcount%2==0 && pfirst1!=NULL)
{
pfirst1->next = pcur;
}
else if (pfirst2!=NULL)
{
pfirst2->next = pcur;
}
}
return phead;
}
int main()
{
PNode head, temp;
head = (PNode)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
for (int i=10; i>0; --i)
{
temp = (PNode)malloc(sizeof(Node));
temp->data = i;
temp->next = head->next;
head->next = temp;
}
head = Reverse_K(head, 3);
return 0;
```

}

The inner loop is the same algorithm as plain old in-place reversal. The only difference is that you have to maintain a few pointers across the inner loop to hook up the k-segments.

```
node *reverse(node *x, int k)
{
node *r = NULL, *p = NULL, *h = NULL;
while (x) {
node *nh = x;
for (int i = 0; i < k && x; i++) {
node *n = x->next;
x->next = p;
p = x;
x = n;
}
if (h) h->next = p;
else r = p;
h = nh;
}
if (h) h->next = NULL;
return r;
}
```

```
//split returns element count <= splitCount
int split(node*& head, node& subHead, int splitCount);
//will change input list
void reverse(node*& head);
void append(node* list, node* node);
void reverseK(node*& globalHead, int count)
{
node* subHead = NULL;
node* newList = NULL;
while(split(globalHead,subHead,count))
{
//got a sublist
reverse(subHead);
if(newList == null)
newList = subHead;
else
append(newList,subHead);
}
}
```

```
def reverseK(head, k):
if head == None:
return head
data = reverse(head, k)
newHead = data[0]
newTail = data[1]
nextHead = data[2]
while nextHead:
data = reverse(nextHead, k)
newTail.setNext(data[0])
newTail = data[1]
nextHead = data[2]
return newHead
# helper function
def reverse(head, k):
originalHead = head
prevHead = None
for i in range(k):
if head == None:
break
tmp = head.getNext()
head.setNext(prevHead)
prevHead = head
head = tmp
return (prevHead, originalHead, head)
```

using it by calling

`head = reverseK(a, 3)`

Hey bharajwad.... how much time is usually given for there questions by the interviewer??

```
void reverseList(Node *h,int K)
{
Node *cur,*next,*prev;
int count=0;
prev=NULL;
cur=h->next;
Node *temp,*tempHead=h;
while(cur!=NULL)
{
count=1;
temp=cur;
while(cur->next!=NULL&&count++<K)
{
printf("point 1\n");
next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
next=cur->next;
cur->next=prev;
tempHead->next=cur;
tempHead=temp;
cur=next;
prev=NULL;
}
}
```

class Node

{

public:

int i_obj;

Node *next;

};

class sknode

{

public:

Node *ptr;

sknode *next;

}*skStart;

void push(Node *ptr)

{

sknode *p = new sknode;

p->ptr = ptr;

p->next = NULL;

if(skStart == NULL)

{

skStart = p;

}

else

{

p->next = skStart;

skStart = p;

}

}

Node *pop()

{

Node *ptr = NULL;

if(skStart != NULL)

{

sknode *temp = skStart;

skStart = skStart->next;

ptr = temp->ptr;

delete temp;

}

return ptr;

}

==========================================

void List::reverseKelemts(int k)

{

Node *ptr = start;

Node *newPtr = NULL;

start = NULL;

int K = k;

int counter = 0;

while(ptr != NULL)

{

counter++;

while(K >= 1)

{

counter++;

if(ptr == NULL)

break;

push(ptr);

ptr = ptr->next;

K--;

}

while(K < 3)

{

counter++;

if(start == NULL)

{

start = pop();

newPtr = start;

}

else

{

newPtr->next = pop();

newPtr = newPtr->next;

newPtr -> next = NULL;

}

K++;

}

}

cout<<"Number of iterations: "<< counter <<endl;

}

```
/**
- check if we can form 1st k elements reversed list
- if yes, update the newhead and newtail of that list
- if no, update the head with newhead and return
- check if we can form next k elemets reversed list
- if yes, append this list to the one formed above and update newtail alone
- if no, (means we are able to make reversed list with less than k elements)
appened this list and update the head with newhead and return head
*/
Node* ReverseKelements(Node * head, int k)
{
/** If list is NULL return */
if(temp == NULL)
return temp;
int flag = 0; /** Helps in identifying new head */
while(1)
{
/** reverse the first k elements
and from the new list */
Node *last = NULL;
Node *temp = head;
Node *temp2, *new_head, *new_tail;
for(int i = 1 ; (i < k)&& (temp != NULL) ; i++)
{
temp2 = temp->next;
temp->next = last;
last = temp;
temp = temp2;
}
/** list end reached before k elements*/
if(temp == NULL)
{
if(flag == 0)
{
/** Total no: of elements in list is less than k */
head = last;
return head;
}
else
{
new_tail->next = last;
head = new_head;
return head;
}
}
/** successfully reversed k elements*/
if(flag == 0)
{
/** first reversed list
store the new head*/
new_head = last;
new_tail = head;
flag = 1;
}
else
{
/** second time onwards*/
new_tail->next = last;
new_tail = head;
}
/** update the iterators*/
head = temp;
last = NULL;
}
```

}

```
{
/* Subroutine to Reverse a Linked List */
void Reverse(struct node** headRef)
{
if(*headRef == NULL || (*headRef)->next == NULL)
return;
else
{
struct node* p = NULL;
struct node* q = *headRef;
struct node* r;
while(q != NULL)
{
r = q->next;
q->next = p;
p = q;
q = r;
}
*headRef = p;
}
}
/* Function to Reverse every K nodes in the given linked list */
void ReverseEveryKNodes(struct node** headRef, int k)
{
int pos = 0;
struct node* NodePtrInOriginalList = *headRef;
struct node* NodeAfterKthNode = NULL;
struct node* NodeBeforeKthNode = NULL;
bool FirstTime = true;
while(NodePtrInOriginalList != NULL)
{
struct node* NodePtrInSubList = NodePtrInOriginalList;
pos = 0;
for(pos = 0; pos < k - 1; pos++)
{
if(NodePtrInOriginalList == NULL)
break;
else
NodePtrInOriginalList = NodePtrInOriginalList->next;
}
if(NodePtrInOriginalList == NULL)
break;
NodeAfterKthNode = NodePtrInOriginalList->next;
NodePtrInOriginalList->next = NULL;
Reverse(&NodePtrInSubList);
if (FirstTime)
{
*headRef = NodePtrInSubList;
FirstTime = false;
}
else
{
NodeBeforeKthNode->next = NodePtrInSubList;
}
while(NodePtrInSubList->next != NULL)
{
NodePtrInSubList = NodePtrInSubList->next;
}
NodeBeforeKthNode = NodePtrInSubList;
NodePtrInSubList->next = NodeAfterKthNode;
NodePtrInOriginalList = NodePtrInSubList->next;
}
}
```

}

struct node *reverse (struct node *head, int k)

- Ali_BABA February 11, 2012{

struct node* current = head;

struct node* next;

struct node* prev = NULL;

int count = 0;

while (current != NULL && count < k)

{

next = current->next;

current->next = prev;

prev = current;

current = next;

count++;

}

if(next != NULL)

{ head->next = reverse(next, k); }

return prev;

}