旋轉鏈接列表C

我目前正在解決列表和函數的求和問題，並且我遇到了這個問題，即將一個鏈表逆時針旋轉k。這裏是相同旋轉鏈接列表C

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。需要幫助:)

來源

2013-09-27 user2714823

什麼也調試器說什麼？ – pm100

認爲需要對列表做些什麼。找到第k個元素;使它成爲新的頭部，並使舊的尾巴成爲老頭。我沒有看到代碼做最後2部分。同時返回新的頭 – pm100

第二個while循環進入列表末尾，ptr-> next =節點使尾部指向舊頭。 node = knode-> next使5個新列表的頭部 – user2714823

你沒有修改原始列表（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-27 18:32:00 SJuan76

返回應該返回的節點，而不是knode對嗎？ – user2714823

從我的代碼（和結果）中讀取，'knode'指向'5'，這是您期望的元素。無論如何測試它。 – SJuan76

SJuan的方法是正確的，但是如果你想在不使用返回值的情況下做到這一點，那麼你需要爲節點使用雙指針。請記住，C會將您傳遞給函數的變量的副本。如果原始根節點是一個指針（我假設它是），則需要製作一個指向指針的指針，否則只是對根節點指針的副本進行更改，而不是實際的根節點指針。

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

來源

2013-09-27 19:09:54 Nate

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-09 19:47:01 Viren

旋轉鏈接列表C

回答

相關問題