Global Scholar Interview Question
Software Engineer / DevelopersCountry: 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;
}