Dear All,
i try to rotate my linked list. I have a linked list with for example the number 197, where each link contains one number.
Now, i have 197. But i want to rotate that like 971 and 719.
I know how to do this with arrays, but how to do in Linked Lists?
Thanks
Same idea applies, different details, of course.
What have you tried? What has you stumped? Can you be more specific about what you're not sure about, and post your code?
Giving advice without seeing the actual code is like diagnosing a patient without actually seeing the patient - you could lose a lot of patients that way.
Wel, that's difficult. With array i should do it like this:
i will calculate the length, and than:
Now, the difficulty is that i cannot give an index to the linked list. So:Code:char temp = number[0]; for(int i=0; i<length-1; i++){ number[i] = number[i+1]; } number[length-1] = temp;
I should start make a link head at "position" one. And the last link in the linked list should go the the first one.... But how to do this...
Peter, I know how to shuffle values in an array.
What I want you to do, is to post your code where you TRY to rotate the order of a linked list, using the simple example you gave, so I can see just where you're logic, is going awry.
It should be something like:
i know the length
lp2 are my links in the linked listCode:void rotation(node** n){ int length = 3; temp = (struct node *) malloc(sizeof(struct node)); temp = n; for(int i=0;i<length;i++){ n = lp2; lp2 = lp2->next; } lp2->next = n; n->next = NULL; }
Last edited by peterderijp; 11-05-2010 at 09:22 AM.
To rotate a linked list, depending on which way to want to rotate either move the last node to the front of the list, or move the first node to the end. I think you see that, but your code doesn't quite match up with what it should be doing. I'm also surprised it doesn't give you warnings. Here's a few hints :
No need to malloc, especially when you throw the space away by reassigning temp in the next statement.
temp = *n, not temp = n. In fact, you probably need *n everywhere you have n in this function.
lp2 isn't assigned to anything to begin with so who knows what value it has when you start. If it is a global it really shouldn't be.
You should be checking for ->next == NULL to find the end of the list, not relying on a fixed length.
Your last two statements should probably have something to do with temp, not n.
the head pointer (n) should only shift one entry. You're shifting it to the last node in your loop which means most of the list will be lost.
This code will have problems if you try to rotate a list with 0 or 1 entries.
Linked lists are easier to understand if you draw out the steps on paper. I'd recommend trying that here.
An even better approach is to use a circular list where the last node points back to the first. This is basically the same as a normal list, except you check for ptr->next == head instead of ptr->next == NULL to find the end of a list. With this setup, all you have to do is move where the head of the list points to (either to head->next or the last node in the list, again depending on which way you're rotating).
Last edited by KCfromNC; 11-05-2010 at 02:52 PM.
