無法扭轉鏈表

我想扭轉鏈表，但是每當我執行下面的函數，我只得到最後一個元素。例如，如果列表中包含11,12,13較早。執行功能後，它僅包含13請指出這個錯誤在我的代碼無法扭轉鏈表

void reverselist() 
{ 
    struct node *a,*b,*c; 
    a=NULL; 
    b=c=start; 

    while(c!=NULL) 
    { 
     c=b->next; 
     b->next=a; 
     a=b; 
     b=c; 
    } 
    start=c; 
}

來源

2012-07-17 OneMoreError

c是幫助指針。

void reverselist() 
{ 
    struct node *a, *b, *c; 
    a=NULL; 
    b=start; 
    while(b!=NULL) 
    { 
     c=b->next 
     b->next=a; 
     a=b 
     b=c 
    } 
    start=a; 
}

來源

2012-07-17 14:24:31

難道你們環路保護確保開始爲空？
如果您沒有使用start來標識列表的第一個元素，那麼您使用的變量仍然指向WAS的第一個元素，它現在是最後一個元素。

來源

2012-07-17 11:30:37

我會作出一個前置的功能，並做了以下內容：

struct node* prepend(struct node* root, int value) 
{ 
    struct node* new_root = malloc(sizeof(struct node)); 
    new_root->next = root; 
    return new_root; 
} 

struct node* reverselist(struct node* inlist) 
{ 
    struct node* outlist = NULL; 

    while(inlist != NULL) { 
     struct node* new_root = prepend(outlist, inlist->value); 
     outlist = new_root; 
     inlist = inlist->next; 
    } 

    return outlist; 
}

沒有測試過這一點，但我猜你掌握它的想法。可能只是你的變量名稱，它們沒有描述任何內容，但我認爲這種方法更清晰，並且更容易理解實際發生的情況。

編輯：

有一個問題，爲什麼我不去做就地，所以在這裏我要回答這個問題：

你能做到就地？你確定你不想保留原始列表嗎？
你需要在現場嗎？ malloc耗費時間/是否是您的代碼中性能至關重要的部分？請記住：過早優化是所有邪惡的根源。

這是第一次執行。它應該工作，而不是優化。它應該還有一個測試，在這個實現被考慮之前編寫，你應該保持這個緩慢的，未優化的實現，直到測試通過，並且你已經證明它會減慢你的使用！

當你有一個通過單元測試，並證明實現要慢時，應該優化代碼，並確保它仍然通過測試，而不會改變測試。

另外，是否有必要就地操作這是答案？在恢復內存之前分配內存怎麼樣，這樣你只有一個分配調用，並且希望獲得不錯的性能提升。

這樣，每個人都很開心，你有一個更清晰的代碼，並避免使用霰彈槍在你家門口出現叔叔的風險。

來源

2012-07-17 11:41:52 martiert

爲什麼分配內存時，你可以在一個循環就地做到這一點？ – JimR 2012-07-17 11:54:53

好吧，如果你的列表有addAtTail/addAtHead類型的調用，向後讀一個列表，向舊列表中添加forwards和delete（）舊列表就好比考慮用0/1條目來毀壞現有列表角落案件等。這是懶惰和效率低下，是的，但我承認這樣做的情況下，操作不頻繁，時間不是本質:) – 2012-07-17 12:07:24

@MartinJames：寫一次，並將其粘貼在片段文件？ :) – JimR 2012-07-17 12:13:23

 

// You should assume that Node has a Node* called next that 
// points to the next item in a list 
// Returns the head of the reversed list if successful, else NULL/0 
Node *reverse(Node *head) 
{ 
    Node *prev = NULL; 

    while(head != NULL) 
    { 
     // Save next since we will destroy it 
     Node *next = head->next; 

     // next and previous are now reversed 
     head->next = prev; 

     // Advance through the list 
     prev = head; 
     head = next; 
    } 
    return previous; 
}

來源

2012-07-17 12:01:39 JimR

無法扭轉鏈表

回答

相關問題