Citrix System Inc Interview Question
Software Engineer / DevelopersBelow code is generic implementation for reversing a chunks in linked list
void reverseListChunk(int k, node** headRef)
{
node* first=0,*second=0,*third=0,*temp=0;
node* prevTemp=0,*revRoot=0,*_head=0,*prevHead=0;
int count=1,k;
_head = *headRef;
temp = *headRef;
prevHead = *headRef;
while(temp)
{
while((temp)&&(count<k))
{
prevTemp=temp;
temp=temp->next;
count++;
}
first=_head;
if(first)
{
second=first->next;
}
while(first != temp)
{
if(second)
{
third=second->next;
second->next=first;
}
else
{
third = 0;
}
first=second;
second=third;
}
if(revRoot == 0)
{
if(temp)
{
revRoot=temp;
}
else
{
revRoot=prevTemp;
}
prevHead->next=0;
}
else
{
if(temp)
{
prevHead->next=temp;
}
else
{
prevHead->next=prevTemp;
}
prevHead=_head;
prevHead->next=0;
}
_head=third;
temp=third;
count=1;
}
*headRef=revRoot;
}
For this case k=2
<pre lang="" line="1" title="CodeMonkey96224" class="run-this">MyList* reverseList(MyList *head)
{
if (NULL == head || NULL == head->next)
return head;
MyList *preNode = head, *curNode = head->next,*nextNode;
MyList *ppreNode = NULL;
MyList *outHead = curNode;
while (curNode)
{
nextNode = curNode->next;
curNode->next = preNode;
preNode->next = nextNode;
if (ppreNode)
ppreNode->next = curNode;
ppreNode = preNode;
preNode = nextNode;
if (preNode)
curNode = preNode->next;
else
break;
}
return outHead;
}
</pre><pre title="CodeMonkey96224" input="yes">
</pre>
node *reverse(node *head)
{
if(head == NULL || head->next == NULL)
return head;
int count = 0;
node *prev = head;
node *cur = head->next;
// Saving the return pointer, which points to the new head
node *ret = cur;
node *fwd;
while(cur!=NULL)
{
//If the node count is odd, you need to set the prev's next pointer to some value
if(count%2 != 0)
{
if(cur->next!=NULL)
{
prev->next->next = cur->next;
}
else
{
prev->next->next = cur;
}
fwd=fwd->next;
prev=cur;
cur=fwd;
}
//else the usual reverse logic
else
{
fwd = cur->next;
cur->next = prev;
prev->next=NULL;
prev = cur;
cur = fwd;
}
count++;
}
return ret;
}
/*iterative method:*/
- Pradeep Rajkumar July 06, 2011void swap_twonodes(struct node** headref)
{
struct node* current=*headref;
struct node* save=NULL;
if(current==NULL) return; /*empty list*/
if(current->next!=NULL) /*set head pointer to correct position*/
*headref=current->next;
while( (current!=NULL) && (current->next!=NULL) ) /*iterate down,to swap the list by two nodes*/
{
save=current->next->next;
current->next->next=current;
current->next=save;
current=save;
}
}