Rotate a linked list

I want to rotate a linked list that contains a number. 123 should be rotated to 231. The function created 23 but the last character stays empty, why?

typedef struct node node;  
struct node{
    char digit;
    node* p;
};

void rotate(node** head){

    node* walk= (*head);
    node* prev= (*head);
    char temp= walk->digit;

    while(walk->p!=NULL){

        walk->digit=walk->p->digit;

        walk= walk->p;
        }

    walk->digit=temp;
}

How I create the list:

node* convert_to_list(int num){ 
   node * curr, * head;

   int i=0,length=0; 

   char *arr=NULL;

   head = NULL;

   length =(int) log10(((double) nu开发者_开发技巧m))+1;
   arr =(char*) malloc((length)*sizeof(char));          //allocate memory 

   sprintf (arr, "%d" ,num); //(num, buf, 10);

    for(i=length;i>=0;i--) {
      curr = (node *)malloc(sizeof(node));
      (curr)->digit =  arr[i];
      (curr)->p = head;
      head = curr;
   }

   curr = head;

   return curr;
}

Your linked list actually has 4 elements.

You should change this line:

for(i = length; i >= 0 ; i--) {

to:

for(i = length - 1; i >= 0; i--) {

because with the former line you're going out of the array (you're accessing arr[length] on the first iteration).

With this change your rotate function works correctly.

You can solve most problems by breaking them down into simpler ones.

Here, I'd write your rotate as follows:

void rotate(node **list) {
    node *head = pop_head(list);
    push_at_end(list, head);
}

node *pop_head(node **list) {
    assert(*list);
    node *head = *list;
    *list = head->p;
    head->p = 0;
    return head;
}

void push_at_end(node **list, node *head) {
    node *end = get_end(*list);
    if (!end) {
        *list = head;
    } else {
        end->p = head;
    }
}

node *get_end(node *head) {
    node *last = 0;
    while (head) {
        last = head;
        head = head->p;
    }
    return last;
}

The problem with your question is that the list is stored backwards, and you have a pointer to previous, instead next. This should have been part of the question (it took me a while to understand that).

Actually, you use head when probably tail would have been better. You should consider storing a pointer to the actual head, and avoid this way copying. In that case, you would only need to adjust pointers. If rotation is going to be a common task, then keeping and updating an extra pointer, may be in a list struct, would pay the effort (could change the task from O(n) to O(1)).

struct _list {
    node * tail;
    node * head;
};

typedef struct _list list;

In any case, the problem with your rotate function is that you are starting with walk and prev at the same node, head.

void rotate(node** head){
    node* walk= (*head);
    node* prev=(*head)->p;
    char temp= walk->digit;

    while(prev!=NULL){

        walk->digit=prev->digit;

        walk= prev;
        prev = prev->p;
    }

    walk->digit=temp;
}

I have written the code for linked list rotation by k nodes in c++. It worked for me perfectly. If you pass k as 1, it will rotate the liked list by 1 node and here it solves the given problem. If you want to rotate the linked list by k nodes, it will still work fine. Please find it below.

Header file :

public:
typedef struct node {

    int data;
    node *next; 

} *Node;

Node head;
void rotateByk(int k);

Following code is for .cpp file.

void DList::rotateByk(int k){
    Node current = head;
    Node kthNode;
    int count = 1;
    while(count<=k && current!=NULL){
        kthNode = current;
        current = current->next;
        count++;
    }

    Node kthNextNode = current;

    while(current->next!=NULL){
        current = current->next;
    }

    current->next = head;
    head = kthNextNode;
    kthNode->next = NULL;

    Node printNode = head;
    while(printNode!=NULL){
        cout << printNode->data << "\t";
        printNode = printNode->next;
    }  
}

Pass k as argument in main method for linked list d1.

d1.rotateByk(1);

Please let me know if you have any queries.