CareerCup

.Question didn't ask to swap alternate pairs instead it is asking for swapping alternate elements. For example: 1-->2-->3-->4-->5 should be transformed to 3-->4-->5-->2-->1.

public static LinkedListNode swapAlternateNodes(final LinkedListNode head) {
    if (head == null || head.next == null) {
        return null;
    }

    LinkedListNode newhead = null;
    LinkedListNode prev = head;
    LinkedListNode cur = prev.next;
    LinkedListNode temp = null;
    while (cur != null && cur.next != null) {
        temp = cur.next;

        prev.next = cur.next.next;
        cur.next = prev;
        temp.next = cur;

        if (newhead == null) {
            newhead = temp;
        } else if (newhead.next == prev) {
            newhead.next = temp;
        } else if (newhead.next.next == prev) {
            newhead.next.next = temp;
        }

        prev = cur;
        cur = cur.next;
    }

    return newhead;
}

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;
	
}

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?

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;
}

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

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

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 ?

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;
}

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;
    }
}

#include<stdio.h>
#include<conio.h>
struct node
{
struct node *next;
int data;
}*front,*rear;
void insert(int ele)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node *));
temp->data=ele;
temp->next=NULL;
if(front==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=temp;
}
}
void display()
{
struct node *temp;
if(front==NULL)
printf("\nempty list");
else
{
printf("\n");
temp=(struct node *)malloc(sizeof(struct node *));
for(temp=front;temp!=NULL;temp=temp->next)
printf("%d",temp->data);
}
}
void swap()
{
int t;
if(front==NULL)
printf("empty list");
else if(front->next==NULL)
printf("single element");
else
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node *));
temp=front;
while(temp!=NULL&&temp->next!=NULL)
{
t=temp->data;
temp->data=temp->next->data;
temp->next->data=t;
temp=temp->next->next;
}
}
}
main()
{
int ch,ele;
clrscr();
while(1)
{
printf("\n1.insert\n2.display\n3.swap\n4.exit");
printf("\nenter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nenter any element");
       scanf("%d",&ele);
insert(ele);
break;
case 2:display();
break;
case 3:swap();
break;
case 4:exit(0);
break;
}
}
}

if(n == null)
return n;
SList head = swap(n);
SList tail = head;

while(tail == null || tail.next != null){
tail.next.next = swap(tail.next.next);
tail = tail.next.next;
}

return head;

}

private static SList swap(SList n){

if(n.next == null || n==null){
return n;
}
SList current = n.next;
SList next = current.next;
n.next = next;
current.next = n;
return current;

}

public boolean swapTwoConsecutiveNodes(){
		if(head == null) {
			System.out.println("List is empty");
			return false;
		}
		Node prev = null;
		Node next = null;
		Node start = head;
		
		head = start.nextNode;
		while(start != null && start.nextNode != null){
			next = start.nextNode;
			if(prev != null) prev.nextNode = next;
			start.nextNode = next.nextNode;
			next.nextNode = start;
			prev = start;
			start = start.nextNode;
		}
		return true;
	}