リンクされたリストを回転する

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

あなたのリンクリストは、実際に4つの要素を持っています。理由（あなたが最初の反復でarr[length]にアクセスしている）あなたは、配列のうちのつもり旧ラインで

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

：

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

へ：

あなたは、この行を変更する必要があります。

この変更により、rotate機能が正しく機能します。

Answer 2

あなたの質問の問題は、リストではなく次、後方格納され、あなたが以前へのポインタを持っているということです。これは質問の一部であったはずです（それを理解するのにはしばらく時間がかかりました）。

実際にはヘッドを使用します。おそらくテールの方が良かったでしょう。実際のヘッドへのポインタを格納することを検討し、このようにコピーしないようにしてください。その場合は、ポインタを調整するだけで済みます。ローテーションが一般的なタスクになる場合は、余分なポインタを保持して更新することは、リスト構造体にある可能性があります（タスクをO（n）からO（1）に変更できる）。いずれの場合においても

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

typedef struct _list list; 

、あなたのローテート機能の問題点は、同じノード、頭で歩くと前に開始されていることです。

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

Answer 3

ほとんどの問題は、単純なものに分解することで解決できます。ここで

次のように、私はあなたの回転を書きたい：

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 4

を私は、C++でk個のノードによってリンクされたリストの回転のためのコードを書かれています。それは私にとって完璧に働いた。 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; 
    } 
} 

リンクリストd1のメインメソッドで、引数としてkを渡します。

d1.rotateByk(1); 

質問がある場合はお知らせください。