單向循環鏈表頭插法圖解：p->next=p 與 rear 指向關係深度解析

代碼現場還原

// 典型頭插法創建單向循環鏈表
Node* p = new Node(x);  // 新節點
p->next = p;            // ① 自指向，形成單節點環
rear = p;               // ② rear 指向該節點

圖解三階段演變

階段 1：`new Node(x)` —— 孤立節點

p ──► [data=x | next=???]   rear = NULL

節點剛分配，`next` 未初始化（野指針），`rear` 仍為空。

階段 2：`p->next = p` —— 自環形成

      ┌──────────────┐
      │              ▼
p ──► [data=x | next]───┘   rear = NULL
      ▲              │
      └──────────────┘

節點 `next` 指向自己，**構成只含一個節點的循環鏈表**。此時鏈表已「閉合」，但外部還沒有句柄持有它。

階段 3：`rear = p` —— 掛上尾指針

rear ──► [data=x | next]───┐
      ▲                    │
      └────────────────────┘

`rear` 指向該節點。**單向循環鏈表慣例：僅維護尾指針 `rear`**，頭節點可通過 `rear->next` O(1) 訪問，尾節點即 `rear` 本身。

為什麼要 `p->next = p`？

• **統一插入邏輯**：無論鏈表空與否，新節點插入「rear 之後、頭節點之前」的代碼完全一致：

  p->next = rear->next; // 新節點 next 指向原頭節點
  rear->next = p;         // rear next 指向新節點
  if (rear == NULL) rear = p; // 空表特判：rear 指向自己
  // 或無需特判：若約定 rear 初始指向一個哨兵節點

• **滿足循環定義**：任意節點沿 `next` 遍歷最終必回到起點，單節點時指向自己是唯一合法狀態

rear 指向「環」還是「節點」？

**指向節點**。`rear` 是 `Node*`，指向鏈表最後一個節點。因為該節點 `next` 指向頭節點，整個環自然可達。**不要理解為指向「環」這個抽象概念**——C 指針只能指向具體內存地址。

後續插入演示：再插入 y，頭插法

Node* q = new Node(y);
q->next = rear->next; // q->next 指向原頭節點 x
rear->next = q;       // x 變為第二個節點，rear->next 指向新頭 y
// rear 不變，仍指向尾節點 x
// 結構： rear→x→y→x... (循環)

圖示：

rear ──► [x | next]──┐
      ▲              │
      │         ┌────┘
      │         ▼
      └───── [y | next]──┘
           (新頭節點)

總結

1. `p->next = p` 使單節點滿足循環鏈表定義（自環）
2. `rear = p` 讓外部獲得入口，**rear 指向尾節點，而非「環」**
3. 循環鏈表**只存 rear** 即可 O(1) 訪問頭尾、實現頭插/尾插/遍歷
4. 理解指針指向「具體節點」而非「抽象結構」，畫圖驗證最直觀

掌握這張圖，單向循環鏈表的增刪改查、Josephus 問題、循環隊列底層實現，全部迎刃而解。