CareerCup

Working code in C++ :-

node* swap_alt(node *root)
{
	if(root == NULL) return NULL;	
	if(root->next == NULL) return root;
	node *cur,*nxt,*tmp,*ret;
	cur=root;
	tmp=NULL;
	while(cur != NULL && cur->next != NULL)
	{
		nxt=cur->next;
		cur->next=nxt->next;
		nxt->next=cur;
		if(tmp == NULL)
		{
			ret = nxt;
			tmp = cur;
		}
		else
		{
			tmp->next = nxt;
			tmp = cur;
		}
		cur=cur->next;
	}
	return ret;
	
}

Hi vinodjayachandran, does these questions are asked in Yahoo, Bangalore??

p=head;s=NULL;
while( p!=NULL && p->next !=NULL && p->next->next !=NULL)
{
q=p->next;
r=q->next;

p->next=r->next; // swap p and r
r->next=q;
q->next=p;

if(s!=NULL)
s->next=r; // connect prev of p to r
s=r; // set r for next iteration
p=q; // for next iteration
}

One general doubt: Does swapping the nodes in such questions means changing the links? Or data swapping is also permissible?

i think according to question
1->2->3->4->5->6->7->8 will be converted to 3->4->1->2->7->8->5->6

now we can find symmetry that if we treat 2 nodes as a single node (1->2 = A, 3->4 = B)
than the problem will be converted to just swapping consecutive node..... just extra precaution in special case if nodes are less than 2 or nodes are in odd number.... and these precaution will be taken in any solution.....

//Swap data only

void List::swapAlternateData()
{
    Node* n1 = root();
    
    if(!n1)
        return;
    
    Node* n2 = n1->next();
    
    while (n2) {
    
        int data = n1->data();
        n1->setData(n2->data());
        n2->setData(data);
        
        if (!n2->next())
            break;
        
        n1 = n2->next();
        n2 = n1->next();
    }
}

//Swap actual nodes

void List::swapAlternateNode()
{
    Node* n1 = root();
    
    if(!n1)
        return;
    
    Node* n2 = n1->next();
    Node* n3 = root();
    while (n2) {
        Node* temp = n2->next();
        n1->setNext(temp);
        n2->setNext(n1);
        
        if (n3 == root())
           setRoot(n2);
        else 
           n3->setNext(n2);
           
        if (!temp)
            break;
        
        n3 = n1; 
        n1 = temp;
        n2 = n1->next();
    }
    
}

hey how did you applied for yahoo@bangalore..thru referral ?

LinkList* swapAlternateNodes(LinkList *ptr)
{
	if(ptr == NULL || ptr->next == NULL)
		return ptr;

	LinkList dummy, *p, *q;
	dummy.next = ptr;
	p = &dummy;
	q = p->next;

	while(q != NULL && q->next != NULL)
	{
		p->next = q->next;
		q->next = p->next->next;
		p->next->next = q;
		p = q;
		q = p->next;
	}
	return dummy.next;
}

void reverse_list()
{
if(head==NULL || head->next==NULL)
return;

mynode *prev, *cur, *temp1;

cur=head;

while(cur!=NULL && cur->next!=NULL)
{
temp1 = cur->next;
cur->next = cur->next->next;
temp1->next = cur;
if(cur!=head)
{
prev->next = temp1;

}
else
head=temp1;
prev = cur;
cur = cur->next;
}
}

node * swap(node *p)
{
    if(p==NULL||p->next==NULL) return p;
    node *q=swap(p->next->next);
    node *r=p->next;
    r->next=p;
    p->next=q;
    return r;
}

Hum, why thinking so hard? Why don't just swap the data value instead of next pointer?

if somebody is looking for code in java, then this is the answer:

public class AlterLinkedList{
    private static void printLinkedList(Node head){
        for(Node curNode=head; curNode!=null; curNode=curNode.next)
            System.out.print(curNode.val+" ");
        System.out.println();
    }
    private static Node alterLinkedList(Node head){
        Node curNode=head;
        Node next1=curNode.next;
        if(next1==null) return curNode;
        curNode.next=next1.next;
        next1.next=curNode;
        head=next1;
        Node next2;
        while(curNode!=null){
            next1=curNode.next;
            if(next1==null) break;
            next2=next1.next;
            if(next2==null) break;
            curNode.next=next2;
            next1.next=next2.next;
            next2.next=next1;
            curNode=next1;
        }
        return head;
    }
    public static void main(String[] argv){
        Node head=new Node(1);
        Node curNode=head;
        for(int i=2; i<=1; i++){
            curNode.next=new Node(i);
            curNode=curNode.next;
        }
        printLinkedList(head);
        head=alterLinkedList(head);
        printLinkedList(head);
    }
}
class Node{
    int val;
    Node next;
    public Node(int val){
        this.val=val;
        this.next=null;
    }
}