Повернуть связанный список

Question

Я хочу повернуть связанный список, который содержит номер. 123 следует повернуть до 231. Функция создала 23, но последний символ остается пустым, почему?

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;
}

Как мне создать список:

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

   int i=0,length=0; 

   char *arr=NULL;

   head = NULL;

   length =(int) log10(((double) num))+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;
}

Answer 1

Вы можете решить большинство проблем, разбив их на более простые.

Здесь я бы написал ваш поворот следующим образом:

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;
}

Answer 2

Ваш связанный список на самом деле имеет 4 элемента.

Вы должны изменить эту строку:

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

на:

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

, потому что с предыдущей строкой вы выходите из массива (вы получаете доступarr[length] на первой итерации).

С этим изменением ваша функция rotate работает правильно.

Answer 3

Я написал код для вращения связанного списка по k узлам в c ++. У меня это сработало отлично. Если вы передадите k как 1, он будет вращать список избранного на 1 узел, и здесь он решит данную проблему. Если вы хотите повернуть связанный список на k узлов, он все равно будет работать нормально. Пожалуйста, найдите его ниже.

Заголовочный файл:

public:
typedef struct node {

    int data;
    node *next; 

} *Node;

Node head;
void rotateByk(int k);

Следующий код для файла .cpp.

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;
    }  
}

Передать k в качестве аргумента в основном методе для связанного списка d1.

d1.rotateByk(1);

Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы.

Answer 4

Проблема с вашим вопросом заключается в том, что список хранится в обратном направлении, и у вас есть указатель на предыдущий , вместо следующий .Это должно было быть частью вопроса (мне потребовалось некоторое время, чтобы понять это).

На самом деле, вы используете head , когда, вероятно, tail было бы лучше.Вам следует рассмотреть возможность хранения указателя на фактическую head и избегать копирования таким способом.В этом случае вам нужно будет только настроить указатели.Если ротация будет обычной задачей, то сохранение и обновление дополнительного указателя, возможно, в структуре list , окупит усилие (может изменить задачу с O (n) на O (1)).

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

typedef struct _list list;

В любом случае, проблема с вашей функцией поворота заключается в том, что вы начинаете с ходьбы и преды в том же узле, 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;
}