Jump to content
xisto Community
Sign in to follow this  
nroot1

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

Recommended Posts

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 by nroot1 (see edit history)

Share this post


Link to post
Share on other sites

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 by spsarolkar (see edit history)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

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 by Unparallelogram (see edit history)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

Terms of Use | Privacy Policy | Guidelines | We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.