C語言實現帶頭結點單鏈表的逆序打印

在之前的文章《C語言實現單鏈表（不帶頭結點）的逆序打印》中，我們詳細介紹了如何對不帶頭結點的單鏈表進行逆序打印。核心思路是遍歷原鏈表，利用頭插法構建一個新鏈表，從而得到逆序後的鏈表。本文將延續這一思路，實現帶頭結點單鏈表的逆序打印。

核心算法思路

帶頭結點的單鏈表與不帶頭結點的結構略有不同：頭結點本身不存儲數據，僅作為鏈表的入口。逆序操作的本質依然是「取出節點，頭插新鏈表」。具體步驟如下：

1. 初始化一個新的帶頭結點鏈表 reverseList。
2. 從原鏈表的第一個數據節點（即 pNode->next）開始遍歷。
3. 對於每個遍歷到的節點 pMove，分配一個新節點 pInsert，複製數據域。
4. 將 pInsert 插入到 reverseList 的頭結點之後（頭插法）。
5. 移動 pMove 到下一個節點，重複上述過程直到鏈表結束。

關鍵代碼實現

/**
 * 逆序帶頭結點的單鏈表
 * @param pNode 原鏈表的頭結點
 * @return 逆序後新鏈表的頭結點
 */
Node *ReverseList(Node *pNode) {
    Node *reverseList;
    InitialList(&reverseList);  // 初始化逆序後的鏈表（含頭結點）

    Node *pMove = pNode->next;  // 跳過頭結點，指向第一個數據節點
    Node *pInsert = NULL;

    while (pMove != NULL) {
        // 分配新節點並複製數據
        pInsert = (Node *)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->element = pMove->element;
        pInsert->next = NULL;

        // 頭插法：新節點插入到 reverseList 頭結點之後
        pInsert->next = reverseList->next;
        reverseList->next = pInsert;

        // 繼續遍歷原鏈表
        pMove = pMove->next;
    }

    printf("%s函數執行，逆序帶頭節點的單鏈表創建成功\n", __FUNCTION__);
    PrintList(reverseList);  // 打印驗證
    return reverseList;
}

代碼關鍵點解析

• 頭結點的處理：原鏈表與新鏈表均含頭結點，遍歷時從 pNode->next 開始，新鏈表初始化時頭結點的 next 為 NULL。
• 內存管理：每次循環內 malloc 一個新節點，避免直接移動原鏈表節點導致原鏈表損壞；若需原地逆序，可調整指針而不分配新內存。
• 頭插法優勢：時間複雜度 O(n)，空間複雜度 O(n)（新建節點），邏輯清晰易懂。

總結

帶頭結點的單鏈表逆序打印，核心在於正確處理頭結點的跳過與新鏈表的初始化。頭插法天然適合構建逆序鏈表，代碼簡潔高效。掌握此技巧，有助於深入理解鏈表指針操作與內存管理。