Swapping First And Last Nodes In A Linked List by only moving pointers

[nroot1 0]

Hey everybody,I've been stuck on this for the past 4 hours now. I need to write a function that will swap the first and last nodes of a linked list, leaving the middle the sameconstraints -cannot move data, only the pointerssample output:linked list a is: 10 20 30 40 50 60 70after swapping: 70 20 30 40 50 60 10so far i'm only able to get this: 70 20 30 40 50 60

void reverse( node * & s)                              {	if(s == NULL || s->p == NULL)   //0 or 1 node	{		//do nothing	}	else if(s->p->p == NULL)  //2 nodes	{		node *temp = s;		s = temp->p;		temp->p = NULL;		s->p = temp;	}	else	{		node *result = NULL;		node *cur = s;		node *walker;		//reverse order		while (cur != NULL)		{			walker = cur->p;			cur->p = result;			result = cur;			cur = walker;		}		s = result;		result = NULL;		cur = s->p;		s->p = NULL;		//reverse all but first & last node		while (cur->p != NULL)		{			walker = cur->p;			cur->p = result;			result = cur;			cur = walker;		}		s->p = result;	}}

there's probably a simpler way to do this...but after working on it for so long my brain is fried lolall i need to do now is figure out a way to get the original first node @ the end of the listthanks!

Edited December 3, 2008 by nroot1 (see edit history)

[spsarolkar 0]

Hey everybody,

 

I've been stuck on this for the past 4 hours now. I need to write a function that will swap the first and last nodes of a linked list, leaving the middle the same

 

constraints

-cannot move data, only the pointers

 

sample output:

 

linked list a is: 10 20 30 40 50 60 70

after swapping: 70 20 30 40 50 60 10

 

so far i'm only able to get this: 70 20 30 40 50 60

 

void reverse( node * & s)                              {	if(s == NULL || s->p == NULL)   //0 or 1 node	{		//do nothing	}	else if(s->p->p == NULL)  //2 nodes	{		node *temp = s;		s = temp->p;		temp->p = NULL;		s->p = temp;	}	else	{		node *result = NULL;		node *cur = s;		node *walker;		//reverse order		while (cur != NULL)		{			walker = cur->p;			cur->p = result;			result = cur;			cur = walker;		}		s = result;		result = NULL;		cur = s->p;		s->p = NULL;		//reverse all but first & last node		while (cur->p != NULL)		{			walker = cur->p;			cur->p = result;			result = cur;			cur = walker;		}		s->p = result;	}}

there's probably a simpler way to do this...but after working on it for so long my brain is fried lol

 

all i need to do now is figure out a way to get the original first node @ the end of the list

 

thanks!

I have rewritten your function

node *firstNode = s;

node *lastNode = s->p;

// make first node as last node

firstNode->p = NULL;

//make last node as first node

lastNode->p = firstNode;

}

else

{

node *cur = s;

//reverse order

node *firstNode=s;

node *secondNode=s->p;

node *secondlastNode=NULL;

while (cur->p != NULL)

{

if(cur->p->p==NULL)

{

secondlastNode=cur;

}

cur=cur->p;

}

//make firstNode as last node

firstNode->p=NULL;

secondlastNode->p = firstNode;

//make make last node as first node

s=secondlastNode->p;

s->p=secondNode;

}

} _linenums:0'>void reverse( node * & s) { if(s == NULL || s->p == NULL) //0 or 1 node { //do nothing } else if(s->p->p == NULL) //2 nodes { node *firstNode = s; node *lastNode = s->p; // make first node as last node firstNode->p = NULL; //make last node as first node lastNode->p = firstNode; } else { node *cur = s; //reverse order node *firstNode=s; node *secondNode=s->p; node *secondlastNode=NULL; while (cur->p != NULL) { if(cur->p->p==NULL) { secondlastNode=cur; } cur=cur->p; } //make firstNode as last node firstNode->p=NULL; secondlastNode->p = firstNode; //make make last node as first node s=secondlastNode->p; s->p=secondNode; }}

Edited January 24, 2009 by spsarolkar (see edit history)

[iGuest 3]

Swapping First And Last Nodes In A Linked List - by only moving pointersSwapping First And Last Nodes In A Linked List

I have a function todo this. Check this out

 Void swapNodes(node *p, node *q) {   printf("nNode to be swapped p = %dt q = %dand", p->val, q->val);   node *prevP, *prevQ, *temp;   // check if one of it is head or not   if(p != head && q != head) {     for(prevP = head; prevP->next != p; prevP = prevP->next);     for(prevQ = head; prevQ->next != q; prevQ = prevQ->next);     prevP->next = q;     temp = q->next;     q->next = p->next;     prevQ->next = p;     p->next = temp;   } else {     prevP = prevQ = NULL;     if(head == p) {     for(prevQ = head; prevQ->next != q; prevQ = prevQ->next);     head = q;     prevQ->next = p;     } else {     for(prevP = head; prevP->next != p; prevP = prevP->next);     head = p;     prevP->next = q;     }     temp = q->next;     q->next = p->next;     p->next = temp;   }}

Regards,

Sandeep Patra

[Unparallelogram 0]

Intuitively, you're trying to move the first element to the end, then the second to last element (previously the last) to the front, using only swaps. So go from the beginning and swap adjacent elements down the line until you hit the end, then repeat again to get the other element back. You can swap the elements just like you would in any other linked list operation. Just move the current pointers into temporary variables and then exchange the corresponding pointers between two adjacent nodes.EDIT: It would help you to abstract the swapping function out.

Edited June 19, 2009 by Unparallelogram (see edit history)