正反向鏈表

我想通過遞歸來反轉鏈表，併爲它寫下如下代碼。該列表是開始時的列表的開始。正反向鏈表

node *reverse_list_recursive(node *list) 
{ 
     node *parent = list; 
     node *current = list->next; 

     if(current == NULL) 
     return parent; 

     else 
     { 
      current = reverse_list_recursive(current); 
      current->next = parent; 
      printf("\n %d %d \n",current->value,parent->value); 
      return parent; 
     } 

    }

我可以看到所有的鏈接都變了。但是，當我嘗試顯示時，我會得到數字的無限打印。當我嘗試將列表中第一個數字的鏈接反向時，我懷疑是有錯誤。

我在做什麼錯？

來源

2010-11-02 Flash

[鏈表遞歸反向（可能重複http://stackoverflow.com/問題/ 2434411/linked-list-recursive-reverse） – 2010-11-02 14:56:35

這不是重複的。不同的錯誤 – 2010-11-02 14:59:10

如果'list == NULL'，這段代碼會做什麼？ – 2010-11-02 15:02:07

您需要設置新的尾部（即老人頭）的下一個指針爲NULL

編輯：這裏是一個遞歸版本

node *reverse_list_recursive(node *list) 
    { 
     node *parent = list; 
     node *child = list->next; 
     node *new_head; 


    if (child == NULL) 
      return parent ; /* new head */ 

    new_head = reverse_list_recursive(child) 
    child->next = parent; /* Old parent is the new child of the old child when reversed */ 
    parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */ 
    return new_head; 
}

來源

2010-11-02 14:57:46

是的......我有點困惑如何做到這一點......你可以提供我的修改>？ – Flash 2010-11-02 15:02:08

當你到達列表的末尾，你返回最後一個節點。最後一個節點的下一個值被分配給自己，因此你會創建一個不一致。如果current爲NULL，則返回NULL，如果返回值爲NULL，則簡單地忽略其餘代碼。

來源

2010-11-02 14:58:10 Neil

不起作用，當我在上面的代碼中做到這一點... :( – Flash 2010-11-02 15:00:34

您忘記更新鏈接列表上第一個項目的next成員。在遞歸調用之前添加parent->next = NULL;。

來源

2010-11-02 14:59:29 kichik

這是行不通的... – Flash 2010-11-02 15:07:32

行後current = reverse_list_recursive(current);您正在將新列表頭存入當前，因此current->next = parent;是錯誤的。新current是新的表頭，但你需要訪問新的列表尾，即OLD current：

node* newhead = reverse_list_recursive(current); 
current->next = parent; 
printf("\n %d %d \n",current->value,parent->value); 
return newhead;

來源

2010-11-02 14:59:52 Vlad

我做了修改後得到相同的輸出 – Flash 2010-11-02 15:09:45

的一些問題，我可以看到：

你需要做的下一個指針新的最後一個節點爲NULL。
如果我最初將傳遞給NULL，那麼您現有的函數將會受到影響。

來源

2010-11-02 15:03:05 codaddict

我正在尋求解決方案來解決第一個問題... – Flash 2010-11-02 15:10:48

我沒有在這裏看到遞歸的好處，迭代也能正常工作。自從我編寫C語言以來，它一直是永恆的（並且沒有簡單的方法來測試以下語法錯誤...或核心轉儲，但您明白了）。

node *reversed_list(node *list) { 
    node *fwd=list;//Purely for readability 
    node *last=null; 
    node *next=null; 
    node *rev=null; 
    do { 
     //Cache next 
     next=fwd->next; 
     //Set current 
     rev=fwd; 
     //Reset next to point back 
     rev->next=last; 
     //Update last 
     last=fwd; 
     //Forward ptr; 
     fwd=next; 
    } while (fwd!=null); 
    return rev; 
}

很肯定你*list是無用的，因爲它現在指向具有->next=null列表的最後一個元素你叫這之後，可能只是更新，而不是返回指針。

更新（遞歸解決方案）

正如其他人所說，新的尾部被搞砸了（點回最後一個元素，但是應該指向空）...和你不回正確的頭，你返回第二個元素。考慮清單a->b->null有你的算法：

p=a, 
c=b; 
c= 
    p=b 
    c=null 
    return b; //b->null 
c=b 
c->next=a //b->a 
return a; //a->b, b->a, a returned 
//But what you wanted is a->null, b->a, and b returned

以下更新的代碼將解決：

node *reverse_list_recursive(node *list) 
    { 
     node *parent = list; 
     node *current = list->next; 

     if(current == NULL) 
     return parent; 

     else 
     { 
      current = reverse_list_recursive(current); 
      current->next = parent; 
      parent->next=null; //Fix tail 
      printf("\n %d %d \n",current->value,parent->value); 
      return current; //Fix head 
     } 

    }

隨着列表a->b->null：

p=a, 
c=b; 
c= 
    p=b 
    c=null 
    return b; //b->null 
c=b 
c->next=a //b->a 
p->next=null //a->null 
return b; // b->a->null

來源

2010-11-02 15:12:13 Rudu

我得到了使用迭代的解決方案。我正在試驗遞歸... – Flash 2010-11-02 15:16:25

夠公平的{下一次可能想提及的問題}，我已經添加了更新的遞歸方法（對新頭和新尾的兩個小改動） – Rudu 2010-11-02 15:48:45

假設我有一個鏈表：

----------  ----------  ----------  ---------- 
| 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL 
----------  ----------  ----------  ----------

你的代碼，將其轉換爲：

----------------------   ---------------------- 
    |     |   |     | 
    v     |   v     | 
----------  ----------  ----------  ---------- 
| 1 | |--->| 2 | | | 3 | | | 4 | | 
----------  ----------  ----------  ---------- 
       ^     | 
        |     | 
        ----------------------

注意，第一個元素仍指向回2.

如果之後加入該行parent->next = NULL前兩個，你會得到：

  ----------------------   ---------------------- 
      |     |   |     | 
      v     |   v     | 
     ----------  ----------  ----------  ---------- 
NULL<---| 1 | | | 2 | | | 3 | | | 4 | | 
     ----------  ----------  ----------  ---------- 
         ^     | 
          |     | 
          ----------------------

這其實是c直立結構。

完整的代碼是：（你只需要打印的當前值每次遞歸調用）

node *reverse_list_recursive(node *list) 
    { 
     node *parent = list; 
     node *current = list->next; 

     if(current == NULL) 
     return parent; 

     else 
     { 
      current = reverse_list_recursive(current); 
      parent->next = NULL; 
      current->next = parent; 
      printf("\n %d \n",current->value); 
      return parent; 
     } 

    }

來源

2010-11-02 16:13:38

這裏去遞歸代碼扭轉一個鏈表。

list * reverse(list * head) 
{ 
    if(head == NULL || head -> link == NULL) 
     return head; 
    list *node = reverse(head- > link); 
    head -> link -> link = head; 
    head -> link = NULL; 
    return node; 
}

來源

2011-04-18 14:48:10 shrishkrish

Severl版本以上不工作作爲OP想要的，所以這裏是我的遞歸版本精細測試：

node * reverseRecursive(node *p,node **head) 
{ 
    if(p->next == NULL) 
    { 
     *head = p; 
      return p; 
    } 
    node *before; 
    before = reverseRecursive(p->next,head); 
    before->next = p; 
    p->next = NULL; 
    return p; 
} 

//call from main 
node*head; 
//adding value 
//assuming now head is now 1->2->3->4->NULL 
node* newHead; 
reverseRecursive(head,&newHead); 
//now now newHead is now 4->3->2->1->NULL

來源

2011-10-10 17:38:48 Gob00st

回答

相關問題