CareerCup

I dont why people have written so huge codes
Here is a small piece of running code
At point of time the situation is like prev->a->b->something

Node swapAdjacentNodes(Node root)
{   Node prev=NULL;
    Node n=root;Node a,b;
    while(n!=NULL && n->next!=NULL)
    {   a=n;
        b=n->next;
        if(prev!=NULL)
        {   prev->next=b;
        }
        else
        {   root=b;
        }
        a->next=b->next;
        b->next=a;
        prev=a;
        n=a->next;

    }
    return root;
}

Is it like every linked list is of type : struct node {struct next, int data}; ok?

Iterate through the list : Find the pair
-----------------------------------
| a | a->next| b | b->next | .......
------------------------------------

a->next = b->next->next
b->next = a

Am I wrong?

Was this question asked at Microsoft DC recruting event..I was asked similar and I provided similar answer.
Eg: Two pointer where second pointer is ahead by 1 place
Increment both the pointers by 2 to find pair od adjacent nodes

I could not complete the code though...

It's not good to use a method only applied for this question. e.g. what if the interviewer want you to swap every 3 adjacent nodes instead of 2? like a->b->c->d->e->f => c->b->a->f->e->d ? I think use recursive function could solve this problem. Can someone give the code?

Nodeptr ReverseN(Nodeptr head, int number) {
 
    if(number < 2) return head;
    Nodeptr pre_sub_list_tail = NULL, curr_ptr = head, reversed_list_head = NULL;
    while(curr_ptr) {
           Nodeptr prev_ptr = NULL, nxt_ptr = NULL, sub_list_tail = NULL, sub_list_head = NULL;
           int count = number;
           while(curr_ptr && count) {
               if(number == count) sub_list_tail = curr_ptr;
               nxt_ptr = curr_ptr->nxtptr;
               curr_ptr->nxtptr = prev_ptr;
               prev_ptr = curr_ptr;
               curr_ptr = nxt_ptr;
               --count;
               if(curr_ptr == NULL) sub_list_head = prev_ptr;
               else if(count == 1) sub_list_head = curr_ptr;
           }
           if(pre_sub_list_tail) {
               pre_sub_list_tail->nxtptr = sub_list_head;
           }else {
               reversed_list_head = sub_list_head;
           }
           pre_sub_list_tail = sub_list_tail;
    }
    return reversed_list_head;
 
}

void CustomInvert(node* a)
{
	node* tmp = a;
        node* prev = NULL;
	while(tmp != NULL && tmp->next != NULL)
	{
		Swap(tmp, tmp->next, prev);
                prev = tmp;
		if(NULL != tmp->next)
		{
			tmp = tmp->next;
		}
	}
}

void Swap(node* a, node* b, node* prevA)
{
	if(NULL == a || NULL == b)
	{
		// log exception();
		return;
	}

    a->next = b->next;
    b->next = a;
    if(NULL != prevA)
    {
	    prevA->next = b;
    }

}

Node* ReverseAdjLists(Node *root)
{
Node *head = root,*curr1= NULL, *curr2= NULL,*next = NULL;
head = root->ptr;
curr1 = root;
curr2 = root->ptr->ptr;
while(curr2 != NULL || curr1->ptr != NULL)
{
next = curr1->ptr;
if(curr2 == NULL)
curr1->ptr = NULL;
else
curr1->ptr = curr2->ptr;
next->ptr = curr1;
if(curr2 == NULL)
curr1->ptr = NULL;
else
curr1 = curr2->ptr->ptr;
if(curr2 != NULL)
{
next = curr2->ptr;
curr2->ptr= curr1->ptr;
next->ptr = curr2;
curr2 = curr1->ptr->ptr;
}
}
return head;

This is a special case of the "every k element reverse problem"
The Original problem was:-
Reverse every k element in the lisk list.
I/P: 1->2->3->4->5->6->7->8->NULL
k=2
O/P: 2->1->4->3->6->5->8->7->NULL

I/P: 1->2->3->4->5->6->7->8->NULL
k=3
O/P: 3->2->1->6->5->4->7->8->NULL

I/P: 1->2->3->4->5->6->7->8->NULL
k=4
O/P: 4->3->2->1->8->7->6->5->NULL

The similar soln can be found

goursaha.freeoda.com/DataStructure/KElementReverseInLinkList.html

MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.

Do take the feedback from employees before joining MS.

And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.

tested and worked fine (recursive):
Node<int>* swapCoupleNodes(Node<int>* node)
{
if ( !node )
return NULL;
else if ( node->next == NULL)
return node;

else
{
Node<int>* temp = node->next->next;
Node<int>* ret = node->next;
node->next->next = node;
node->next = swapCoupleNodes(temp);
return ret;
}

}

void swap (node *list)
{
node *temp = list->next; // temporary variable
list->next=list->next->next;
list->next->next=list;
list=temp;
if(list->next != NULL)
swap(list->next->next);
}

1.linked list is given pointed by head
2.temp1=head,temp2=temp1->next;
while(temp2)
{
swap(temp1,temp2);
temp1=temp1->next;
temp2=temp1->next;
}
swap(temp1,temp2)
{
temp3=temp1;
temp1=temp2;
temp2=temp3;
}

MAIN HOON BOND!!!!!!!!!!!

main bhi hoon superbond

Can anyone please explain the logic on how to do this problem?

I have come up with a recursive solution and i found this to be more intuitive

linkedlist changeAlternate(linkedlist head)
	{	
		
		if(head==null||head.next==null)
		return head; 
			
		linkedlist temp2=head.next;
		linkedlist temp = head.next.next;
		head.next.next=head;
		head.next=changeAlternate(temp);
		head=temp2;
		return temp2;
	}