Microsoft Interview Question
Software Engineer in TestsCountry: India
I guess above sol need some modifications bt nice thought :)
node reverse(node head,int n)
{
int k = n; // need to initialize k
node p,q=null,temp=head;
if(head==null)
return null;
while(k--)
{
p=q;
q=temp;
temp=temp.next;
q.next=p;
}
head.next=reverse(temp,n); // pass n instead of n
return q;
}
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;
}
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
- techcoder October 19, 2011