鏈接列表反轉

我想弄清楚這種方法如何可以用於反轉鏈接列表。但我不知道這裏發生了什麼。我需要知道它是如何將指針切換到另一個方向的。感謝幫助。鏈接列表反轉

void reverse(struct node** head_ref) 
{ 
     Node* prev = NULL; 
     Node* current = *head_ref; 
     Node* next; 
     while (current != NULL) 
     { 
      next = current->next; 
      current->next = prev; 
      prev = current; 
      current = next; 
     } 
     *head_ref = prev; 
}

來源

2013-11-04 14K

創建一個小鏈接列表，也許有3個元素。然後用調試器調用reverse（）和單步調試，仔細注意發生的所有事情。 –

@MartinJames我試圖通過使用圖來切換指針。但搞砸了。 – 14K

翻轉雙向鏈表的重點是什麼？事實上，大多數事情不應該被顛倒，因此C++的反向迭代器 – aaronman

有沒有真正的需要扭轉這個名單，因爲它的雙鏈接，但這裏的這個功能是如何工作的？

我們開始與元素的列表：

list: [A -> B -> C -> NULL] 
current: A 
next: UNINITIALISED 
prev: NULL

首先，我們看看元素A.它的'下一個'指針指向B.我們將該指針指向B並將其備份到本地變量'next'中。然後我們把A的'next'指向當前的本地'previous'，它現在是NULL。接下來，我們更新本地的「上一個」指針並將其設置爲A，最後設置本地「當前」指針指向的「未來」，這是元素B.

list: [A -> NULL], [B -> C -> NULL] 
current: B 
next: B 
prev: A

現在，我們已經完成了與循環的第一次迭代，所以我們回到頂部並重新進行。我們將本地'下一個'設置爲B的'下一個'，這是C.我們將B的'下一個'設置爲當前本地'前一個'，這是A.最後，我們更新本地'之前'爲B並更新當地的「當前」是C.

list: [B -> A -> NULL], [C -> NULL] 
current: C 
next: C 
prev: B

模式現在是相當明顯的，所以我會跳過演練...

現在

list: [C -> B -> A -> NULL] 
current: NULL 
next: NULL 
prev: C

，電流爲NULL，所以在布爾表達式while循環返回false，我們退出循環。發生的最後一件事情是，列表中新的「頭部」指針現在被設置爲指向新的頭部。C.

來源

2013-11-06 01:51:34 mirichan

鏈接列表反轉

回答

相關問題