Rotate Linked list

This is a discussion on Rotate Linked list within the C Programming forums, part of the General Programming Boards category; Dear All, i try to rotate my linked list. I have a linked list with for example the number 197, ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    17

    Rotate Linked list

    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

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  3. #3
    Registered User
    Join Date
    Sep 2010
    Posts
    17
    Wel, that's difficult. With array i should do it like this:

    i will calculate the length, and than:
    Code:
    	char temp = number[0];
    	for(int i=0; i<length-1; i++){
    		number[i] = number[i+1];
    	}
    	number[length-1] = temp;
    Now, the difficulty is that i cannot give an index to the linked list. So:

    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...

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  5. #5
    Registered User
    Join Date
    Sep 2010
    Posts
    17
    It should be something like:
    i know the length
    Code:
    
    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;
    
    	
    }
    lp2 are my links in the linked list
    Last edited by peterderijp; 11-05-2010 at 09:22 AM.

  6. #6
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21