CareerCup

Dont think the solutions above will give right response
here's my recursive algo
node* swap (node* root)
{
if (root==NULL) return NULL;
if (root->link==NULL) return root;
node* first, second;
first = root;
second = root->link;
first->link= swap(second->link);
second->link=first;
}

algopadawan(dot)blogspot(dot)com/2012/05/k-reverse-linked-list(dot)html

void swap()
{
int len=count();
node *start=p;
node *prev=NULL;
node *temp=NULL;
for(int i=0;i<len && start !=NULL;i++)
{
if(start==p)
{
temp=start->next;
start->next=start->next->next;
temp->next=start;
prev=start;
start=start->next;
p=temp;
}
else
{
temp=start->next;
start->next=start->next->next;
temp->next=start;
prev->next=temp;
prev=start;
start=start->next;
}
}
}

struct node* exchange(struct node* node) {
if(node==NULL || node->next==NULL) return node;
struct node* p=node, *q=node->next;
do {
p->next = q->next;
if(p==node) node=q;
q->next=p;
p=p->next;
if(p != NULL) q=p->next;
} while(p!=NULL || q!=NULL);
return node; }

int pairwise()
                {
                        struct node* t=p;
                        struct node* s;
                        while(t!=NULL && t->l!=NULL)
                        {
                                s=t->l;
                                t->l=t->l->l;
                                s->l=t;
                                if(t==p)
                                  p=s;
                                t=t->l;
                                if(t->l!=NULL)
                                        s->l->l=t->l;

                        }
                }

void swap(int *a, int *b);
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
struct node *temp = head;

/* Traverse further only if there are at-least two nodes left */
while(temp != NULL && temp->next != NULL)
{
/* Swap data of node with its next node's data */
swap(&temp->data, &temp->next->data);

/* Move temp by 2 for the next pair */
temp = temp->next->next;
}
}

start = head
j = 1;
while(start != null)
n = start;
n = n->next;
j++;
if(j == jump)
{
j = 1;
saveNext = n->next;
n->next = null;
node* last = Reverse(start);
last->next = saveNext;
start = saveNext;
}

Node * Reverse(Node* n)
{
prev = null;
cur = n;
next;
while(cur != null)
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}

return prev;

> 1->2->3->4->5->1(this is circular one)

Is the 1 at the beginning and the end the same node?

they always ask to write a running code on paper. so practice to write a code...
anyone with the code !!

there is nothing to test about the logic in this question, interviewer is trying to test the pointer manipulation. here we need to handle specially for head pointer. i.e for Head node and Head-> next nodes swap , swap using **Headref, i,e change the head node points to...

SwapTwoNodes(struct node **headref)
{

//code to swap head node
struct node *temp;
temp = *headref;
**headref= temp->link;
temp->link=*headref->link;
*headref->link=temp;

//now code for swapping rest of the nodes
while(temp->link!=*headref)
{
temp2=temp1->link;
temp->link=temp2->link;
temp2->link=temp->link->link;
temp->link->link=temp2;
temp=temp2;
}

}

assume temp1 is a typo for temp

Will it be eassier to just swap data instead of pointer??
Also, we can use recursion to perform swapping for simple linked list...I am not sure if that can be done for circular linked list too.

//L is header

Node t1,t1,temp;
if(L->next!=NULL)
{
t1=L->next;
t2==t1->next;
temp=t2->next;
L->next=t2;
t2->next=t1;
t1->next=temp;
temp=t1;
}

while(temp!=null)
{
t1=temp->next;
t2=t1->next;
t3=t2->next;
temp->next=t2;
t2->next=t1;
t1->next=t3;
temp=temp->next->next;
}

boundary case : either you are at last node or you are not
if you get circular list, two case might happen:
a.)either your next node refers to first node(means you have one next node with which you can swap) - swap and quit
b.) or next node refers to second node in list(means you are at the last node) - quit here

Here is the simplest I could get it:

Node* FlipPairsList(Node* list)
{
    if (!list)
    {
        return list;
    }
    else if (!list->next) 
    {
        return list;
    }
    else
    {
        Node* t = 0;
        Node* p = list;
        list = list->next;
        while (p && p->next)
        {
            t = p->next->next;
            p->next->next = p;
            if (t == 0)
            {
                p->next = 0;
            }
            else if (t->next == 0)
            {
                p->next = t;
            }
            else
            {
                p->next = t->next;
            }
            p = t;
        }
        return list;
    }
}

Here is the C++ Code for this problem

bool CList::SwapAdjacent()
{
	SNode *pList = m_pRoot;
	bool fIsCircular = false;
	if(!pList || !pList->pNext)
		return fIsCircular;


	SNode *pNext = NULL, *pTrack = pList;
	int nData = 0;
	
	while((pList != NULL && pList->pNext!= NULL))
	{
		// case where the list has odd elements and is circular
		if(pList->pNext == pTrack)
		{
			fIsCircular = true;
			break;
		}
		
		pNext = pList->pNext;
		nData = pList->nData;
		pList->nData = pNext->nData;
		pNext->nData = nData;

		pList = pNext->pNext;
		// case where the list has even elements and is circular
		if(pList == pTrack)
		{
			fIsCircular = true;
			break;
		}
	}
	return fIsCircular;
}

There r two way to solve this prob :
1.Without Recursion.
2.With Recursion.

[1]Without Recursion:

node* swapList(node *firstNode)
{
node *head,*prev;

if(node==NULL) //if List is empty
{
printf("List is Empty");
}

if(node->link==NULL)//if List is having Single node
{
printf("List is having single node");
head=firstNode;
}

if(firstNode->link->ink!=NULL)//to set head of the new list.It will swap only starting two nodes.
{
head=firstNode->link;
firstNode->link=head->link;
head->link=firstNode;
}

while(firstNode->link->link!=NULL)//swap remaining nodes
{
prev=firstNode;
firstNode=firstNode->link;
prev->link=firstNode->link;
firstNode->link=firstNode->link->link;
prev->link->link=firstNode;
}

return head;
}

[2]With recursion:

node* swapList(node *firstNode)
{
node *head,*prev;

if(node==NULL) //if List is empty
{
printf("List is Empty");
}

if(node->link==NULL)//if List is having Single node
{
printf("List is having single node");
head=firstNode;
}

if(firstNode->link->ink!=NULL)//to set head of the new list.It will swap only starting two nodes.
{
head=firstNode->link;
firstNode->link=head->link;
head->link=firstNode;
}

swap(firstNode);

return head;
}
//--------------------------------
swap(node *ptr)
{

node *prev;
if(ptr->link->link!=NULL)
{
ptr=ptr->link->link;
swap(ptr);
}
prev=ptr;
ptr=ptr->link;

prev->link=ptr->link;
ptr->link=ptr->link->link;
prev->link->link=ptr;
}

ptr=head;
pptr=NULL;
while(ptr->next!=NULL)
{
temp=ptr->next->next;
ptr->next->next=ptr;
if(pptr!=NULL)
{
pptr->next=ptr->next;
}
pptr=ptr;
ptr->next=temp;

ptr=ptr->next;
}

//looking forward to constructive suggestions

swap_pairs (list *p1)
{
    list *temp = NULL, *prev = NULL;
    while (p1 != NULL) {
        if (p1->next) {
            temp = p1->next;
            p1->next = temp->next;
            temp->next = p1;
            if (prev) {
                prev->next = temp;
                prev = p1;
            }
        }
    }
}

struct node *swapper2(struct node *l1)
{
struct node *head;
struct node *p *q,*r;
p=l1;
q=l1->next;
head=p;
count=2;
while(q && --count)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
head->next=swapper2(q);
return p;


}

Wow, this question has really made its rounds since I started asking it in interviews :)

Take a look at this iterative solution. Recursively, it is a bit shorter, but I usually prefer iterative solutions.

node* swap_pairwise(node* root) {
	if (root == NULL || root->next == NULL) return root;

	// Prepend a node to root to reduce special-casing.
	std::auto_ptr<node> aux(new node(0));
	aux->next = root;
	node* n1 = aux.get();

	while (n1->next != NULL && n1->next->next != NULL) {
		node *n2 = n1->next, *n3 = n2->next, *n4 = n3->next;

		n1->next = n3;
		n3->next = n2;
		n2->next = n4;

		n1 = n2;
	}
	return aux->next;
}

public void Interchange()
        {
            Node<T> current = _head;
            while (current != null)
            {
                var tuple = Tuple.Create(current, current.Next, current.Next?.Next, current.Next?.Next?.Next);
                if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)
                {
                    tuple.Item1.Next = tuple.Item3;
                    tuple.Item3.Next = tuple.Item2;
                    tuple.Item2.Next = tuple.Item4;
                }
                current = current.Next?.Next;
            }
        }

public void Interchange()

{

Node<T> current = _head;

while (current != null)

{

var tuple = Tuple.Create(current, current.Next, current.Next?.Next,  current.Next?.Next?.Next);

if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)

{

tuple.Item1.Next = tuple.Item3;

tuple.Item3.Next = tuple.Item2;

tuple.Item2.Next = tuple.Item4;

}

current = current.Next?.Next;

}

}

public void Interchange()
        {
            Node<T> current = _head;
            while (current != null)
            {
                var tuple = Tuple.Create(current, current.Next, current.Next?.Next, current.Next?.Next?.Next);
                if (tuple.Item1 != null && tuple.Item2 != null && tuple.Item3 != null)
                {
                    tuple.Item1.Next = tuple.Item3;
                    tuple.Item3.Next = tuple.Item2;
                    tuple.Item2.Next = tuple.Item4;
                }
                current = current.Next?.Next;
            }
        }

Node* reverse(Node *Root)
    {
        Node* nRoot,temp ;
        if(Root==null) return null;
        nRoot = Root->next;
        if(nRoot==null) return Root;
        
        while(root!=null)
        {
            temp = root->next;
            root->next = temp->next;
            temp->next = root;
            root=root->next; 
        } 
      return nRoot;
    }

tum sab log mera loda chuso