總結(jié)歸納

• 頭結(jié)點(diǎn)可以沒有，頭指針必須有。訪問(wèn)整個(gè)鏈表，是用過(guò)遍歷頭指針來(lái)進(jìn)行的。
• 這里沒有特別的設(shè)置一個(gè)頭指針，因?yàn)楫?dāng)指針指向整個(gè)鏈表 L 時(shí)，該指針的實(shí)現(xiàn)效果就是指向頭指針。
• 不帶頭結(jié)點(diǎn)的單鏈表，即單鏈表的第一個(gè)結(jié)點(diǎn)就存儲(chǔ)數(shù)據(jù)，頭指針也指向第一個(gè)結(jié)點(diǎn)；帶頭結(jié)點(diǎn)的單鏈表，第一個(gè)結(jié)點(diǎn)是頭結(jié)點(diǎn)，不存儲(chǔ)數(shù)據(jù)，從頭結(jié)點(diǎn)的 next 開始存儲(chǔ)，頭指針可以從頭結(jié)點(diǎn)的 next 開始遍歷。
• 對(duì)于結(jié)點(diǎn)的前插操作，找到對(duì)應(yīng)位置的結(jié)點(diǎn)，設(shè)新結(jié)點(diǎn)為該節(jié)點(diǎn)的后繼結(jié)點(diǎn)，將該結(jié)點(diǎn)的 data 后移至新結(jié)點(diǎn)的 data，以此來(lái)模擬結(jié)點(diǎn)的后移，并且時(shí)間復(fù)雜度為 O(1)，我愿稱之為“偷天換日”。
• 在 DeleteNode 函數(shù)中（刪除指定結(jié)點(diǎn)），存在一處 bug ，當(dāng)刪除結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)時(shí)，由于該結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，該函數(shù)會(huì)報(bào)錯(cuò)，初步認(rèn)為只能通過(guò) DeleteNextLNode函數(shù)（刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)）來(lái)實(shí)現(xiàn)刪除最后一個(gè)結(jié)點(diǎn)的操作。
• 大多數(shù)情況下，單鏈表的查詢、插入、刪除的平均時(shí)間復(fù)雜度都是O(n)，因?yàn)橐闅v頭結(jié)點(diǎn)開始查找。但如果對(duì)指定結(jié)點(diǎn)進(jìn)行插入和刪除，則時(shí)間復(fù)雜度為O(1)，因?yàn)椴恍枰偻ㄟ^(guò)遍歷找到指定的結(jié)點(diǎn)。要具體分析。

代碼實(shí)現(xiàn)

#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

// 單鏈表結(jié)點(diǎn)
struct LNode {
    int data;    // 數(shù)據(jù)域
    LNode *next; // 指針域
};

typedef LNode LNode;     // LNode表示單鏈表的一個(gè)結(jié)點(diǎn)
typedef LNode *LinkList; // LinkList表示一個(gè)單鏈表

// 初始化單鏈表
void InitList(LinkList &L) {
    L = new LNode;
    // L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
}

// 判斷單鏈表是否為空
bool Empty(LinkList &L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

// 獲取單鏈表長(zhǎng)度
int GetLength(LinkList &L) {
    LNode *p = L->next;
    int length = 0;
    while (p != NULL) {
        p = p->next;
        length++;
    }
    return length;
}

// 按位查找：查找第i個(gè)結(jié)點(diǎn)
LNode *GetElem(LinkList &L, int i) {
    if (i < 0) {
        return NULL; // i值不合法
    }
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找：查找數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)
LNode *GetLNode(LinkList &L, int e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

// 頭插法建立單鏈表
LinkList List_HeadInsert(LinkList &L) {
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->data = e;
        s->next = L->next;
        L->next = s;
        cin >> e;
    }
    return L;
}

// 尾插法建立單鏈表
LinkList List_TailInsert(LinkList &L) {
    LNode *r = L; // r為尾指針
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->next = r->next;
        s->data = e;
        r->next = s;
        r = s; // 將r置為新的尾指針
        cin >> e;
    }
    r->next = NULL; // 尾指針的next置為NULL
    return L;
}

// 前插操作：在p結(jié)點(diǎn)之前插入數(shù)據(jù)e
bool InsertPriorNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s->next = p->next;
    s->data = p->data; // 數(shù)據(jù)后移，模擬結(jié)點(diǎn)后移
    p->next = s;
    p->data = e; // 將前結(jié)點(diǎn)置為新插入的結(jié)點(diǎn)
    return true;
}

// 后插操作：在p結(jié)點(diǎn)之后插入數(shù)據(jù)e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *q = new LNode;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
    if (i < 1) { // i值不合法
        return false;
    }
    LNode *p = GetElem(L, i - 1); // 遍歷查找i-1個(gè)結(jié)點(diǎn)
    InsertNextNode(p, 5244);      // 使用后插法
    /*  // 使用前插法，達(dá)到同樣效果
    LNode *p = GetElem(L, i);
    InsertPriorNode(p, 5244);
    */
    return true;
}

// 刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)
bool DeleteNextDNode(LNode *p) {
    if (p == NULL || p->next == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;
    p->next = s->next;
    delete s;
    return true;
}

// 刪除指定結(jié)點(diǎn)
bool DeleteNode(LNode *p) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;       // q指向被刪除結(jié)點(diǎn)
    p->data = s->data; // 數(shù)據(jù)前移，模擬結(jié)點(diǎn)前移
    p->next = s->next; // 斷開與被刪除結(jié)點(diǎn)的聯(lián)系
    delete s;
    return true;
}

// 按位序刪除
bool ListDelte(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    /*  // 按結(jié)點(diǎn)刪除，實(shí)現(xiàn)同樣效果
    LNode *p = GetElem(L, i);  // 被刪除結(jié)點(diǎn)
    e = p->data;
    DeleteNode(p);
    */
    LNode *p = GetElem(L, i - 1);
    e = p->next->data;
    DeleteNextDNode(p);  // 刪除前一結(jié)點(diǎn)的后繼結(jié)點(diǎn)
    return true;
}

// 遍歷單鏈表
void TraverseList(LinkList &L) {
    if (L->next == NULL) {
        return;
    }
    LNode *p = L->next; // 指向頭指針
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    InitList(L);

    L = List_TailInsert(L); // 尾插法
    // L = List_HeadInsert(L);  // 頭插法
    TraverseList(L);

    InserstList(L, 1, 5244);
    TraverseList(L);

    int e = -1;
    ListDelte(L, 3, e);
    cout << "被刪除的值：" << e << endl;
    TraverseList(L);
    cout << "長(zhǎng)度：" << GetLength(L) << endl;
    return 0;
}