Yahoo Interview Question
Software Engineer / DevelopersWorking 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;
}
wrong solution. 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;
}
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;
}
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();
}
}
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;
}
This code is for swapping two consecutive nodes which can be easily modified for this problem as follows
node * swap(node *p)
{
if(p==NULL||p->next==NULL || p->next->next==NULL || p->next->next->next==NULL) return p;
node *q=swap(p->next->next->next->next);
node *r=p->next->next;
r->next->next=p;
p->next->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;
}
.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.
- zahidbuet106 June 13, 2014