3

私は現在、リストと関数の合計の問題を解決していますが、この質問に出くわしました。つまり、リンクされたリストを k 反時計回りに回転させます。ここに同じコードがあります

void rotate_k(struct list *node,int k)
{
   int count=0;
   struct list *knode,*ptr=node;
   while(ptr!=NULL && count < k)
    {
      ptr=ptr->next;
      count++; 
     }
    knode=ptr;
    while(ptr->next!=NULL)
     {
      ptr=ptr->next;
      }
    ptr->next =node;
    node=knode->next;
    knode->next=NULL;
  }

入力が 1->2->3->4->5->6 で k=4 の場合を考えてみましょう。

出力は 5->6->1->2->3->4 である必要がありますが、コードは出力 1->2->3->4->5 を提供します。助けが必要です:)

4

3 に答える 3

3

元のリストを変更していません (nodeパラメーター)

struct list *rotate_k(struct list *node,int k)
{
   int count=0;
   struct list *knode,*ptr=node;
   while(ptr!=NULL && count < k)
   {
      ptr=ptr->next;
      count++; 
   }
   knode=ptr;
   while(ptr->next!=NULL)
   {
      ptr=ptr->next;
   }
   ptr->next =node;
   node=knode->next;     
   knode->next=NULL;

   return knode; //<-- THIS IS THE NEW LIST
}

また、knode->next=NULL変ですよね～。以前の（だった）ノードで行う必要がありますknode（これが結果から6を削除しているものです）。

于 2013-09-27T18:32:00.020 に答える
0 
void rotate_list_right(listnode** head, int k)
    {
    if( !head || !*head )
        {
        printf( "\nrotate_list_right: empty list = so return \n" );
        return;
        }
    if( k < 1 )
        {
        printf( "\nrotate_list_right:invalid input: k must be >= 1 \n" );
        return;
        }

    listnode* post = *head;
    listnode* curr = *head;

    /* move post by k nodes */
    while(k--)
        {
        post = post->next;
        if( !post ) /* k is bigger than length of the list */
            {
            printf( "\nrotate_list_right:invalid input: k must be smaller than list size \n" );
            return;
            }
        }

    /* move curr to kth-last node */
    while(post->next)
        {
        curr = curr->next;
        post = post->next;
        }

    /* currs' next is new header */
    listnode* tmp = *head;
    *head = curr->next;
    curr->next = 0;

    //join post
    post->next = tmp;
    }
于 2014-07-09T19:47:01.557 に答える