C/C++ 雙鏈表之逆序的實例詳解
一、結點結構
雙向鏈表的數據結構定義如下：
typedef struct node { ElemType data; struct node *prior struct node *next; }list;其中，ElemType可以是任意數據類型如int、float或者char等，在算法中，規定其默認為int類型。
二、帶頭結點
本文描述的是雙向鏈表逆序，鏈表逆序需要維護3個指針，分別指向前一個節點、當前節點和下一個節點，具體代碼如下：
list *reverselist(list *head) { if ((NULL == head) || (NULL == head->next)) { return head; } list *p1=head->next, *p2=p1->next, *p3=NULL; p1->next = NULL; while (p2) { p3 = p2->next; // 保存當前結點的下一結點 p2->next = p1; // 改變當前結點的next域，指向它的前一個結點 p1->prior = p2; // 改變前一個結點的prior域，指向它的后一個結點 p1 = p2; // 指針移到下一個結點 p2 = p3; } head->next = p1; // 恢復頭結點 p1->prior = head; return head; }在鏈表逆序過程中，非常重要的一點是要防止斷鏈問題，因此，在移動指針逆序某個結點時，需要用一個指針指向該結點的下一結點，防止下一結點丟失。
三、不帶頭結點
list *reverselist(list *head) { if ((NULL == head) || (NULL == head->next)) { return head; } list *p1=head, *p2=p1->next, *p3=NULL; p1->next = NULL; while (p2) { p3 = p2->next; p2->next = p1; p1->prior = p2; p1 = p2; p2 = p3; } head = p1; return head; } 不帶頭結點的鏈表逆序與帶頭結點的區別在于紅色部分代碼，即初始p1指向的是第一個結點而不是頭結點，最后head直接指向p1而不是用其next來指向p1。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
