2. 链表

本资料共 24 道链表代码题。动手前必须先确认：是否带头结点、是否循环、是否双向、是否有序、能否新建结点、是否要保留输入链。修改 next 前先保存后继，释放结点后不得再访问它。

2.0 统一定义与内存约定

#include <ostream>

using ElemType = int;

struct LNode {
    ElemType data;
    LNode *next;
};

struct DNode {
    ElemType data;
    DNode *prior;
    DNode *next;
};

• “带头结点单链表”中，head 指向不存放有效数据的哨兵，首元结点为 head->next。
• “不带头结点单链表”中，链表指针本身就是首元指针，空表为 nullptr。
• 代码统一使用 new/delete；不能把 new 与 free 混用。

---

2.1 代码题 1：递归删除无头链表中所有 x

void DeleteAllNoHeadRec(LNode *&L, ElemType x) {
    if (L == nullptr) return;

    if (L->data == x) {
        LNode *q = L;
        L = L->next;
        delete q;
        DeleteAllNoHeadRec(L, x); // 新首元仍可能等于 x
    } else {
        DeleteAllNoHeadRec(L->next, x);
    }
}

• 引用参数 LNode *&L 允许递归层直接改写当前子链入口，所以能删除首元结点。
• 时间 $O(n)$；递归栈最坏 $O(n)$，长链应优先考虑迭代版。

---

2.2 代码题 2：删除带头链表中所有 x

void DeleteAllWithHead(LNode *head, ElemType x) {
    LNode *pre = head;
    while (pre->next != nullptr) {
        if (pre->next->data == x) {
            LNode *q = pre->next;
            pre->next = q->next;
            delete q;
            // pre 不动，继续检查新的 pre->next。
        } else {
            pre = pre->next;
        }
    }
}

• 连续多个 x 时，删除后前驱不能前移；否则会漏删。
• 时间 $O(n)$、空间 $O(1)$。

---

2.3 代码题 3：删除带头链表中第一个 x

bool DeleteFirstWithHead(LNode *head, ElemType x) {
    LNode *pre = head;
    while (pre->next != nullptr && pre->next->data != x)
        pre = pre->next;

    if (pre->next == nullptr) return false;
    LNode *q = pre->next;
    pre->next = q->next;
    delete q;
    return true;
}

• 成功后立即返回，只删除第一次出现的 x；未找到返回 false。
• 时间 $O(n)$、空间 $O(1)$。

---

2.4 代码题 4：从尾到头输出单链表

void PrintReverse(const LNode *first, std::ostream &out) {
    if (first == nullptr) return;
    PrintReverse(first->next, out);
    out << first->data << ' ';
}

• 带头结点时调用 PrintReverse(head->next, out)，不能输出头结点数据域。
• 时间 $O(n)$，递归栈 $O(n)$；若不允许递归，可用显式栈保存结点指针。

---

2.5 代码题 5：带头单链表原地逆置

void ReverseWithHead(LNode *head) {
    LNode *p = head->next;
    head->next = nullptr;

    while (p != nullptr) {
        LNode *next = p->next;
        p->next = head->next;
        head->next = p;
        p = next;
    }
}

• 先保存 next，再把当前结点头插；顺序颠倒会丢失未处理链。
• 时间 $O(n)$、空间 $O(1)$。

---

2.6 代码题 6：删除值在开区间 (s,t) 内的结点

bool DeleteOpenRange(LNode *head, ElemType s, ElemType t) {
    if (s >= t) return false;

    LNode *pre = head;
    while (pre->next != nullptr) {
        ElemType value = pre->next->data;
        if (value > s && value < t) {
            LNode *q = pre->next;
            pre->next = q->next;
            delete q;
        } else {
            pre = pre->next;
        }
    }
    return true;
}

• 题目明确“不包含 $s,t$”，所以判断必须是严格不等式。
• 时间 $O(n)$、空间 $O(1)$。

---

2.7 代码题 7：删除带头链表的唯一最小结点

bool DeleteUniqueMinWithHead(LNode *head, ElemType &minValue) {
    if (head->next == nullptr) return false;

    LNode *minPre = head;
    for (LNode *pre = head; pre->next != nullptr; pre = pre->next)
        if (pre->next->data < minPre->next->data)
            minPre = pre;

    LNode *q = minPre->next;
    minValue = q->data;
    minPre->next = q->next;
    delete q;
    return true;
}

• 保存最小结点的前驱可在一次遍历后 $O(1)$ 断链。
• 时间 $O(n)$、空间 $O(1)$；“最小值唯一”使相等时无需决定删哪一个。

---

2.8 代码题 8：删除无头链表的唯一最小结点

bool DeleteUniqueMinNoHead(LNode *&L, ElemType &minValue) {
    if (L == nullptr) return false;

    LNode *minNode = L;
    LNode *minPre = nullptr;
    LNode *pre = nullptr;

    for (LNode *p = L; p != nullptr; p = p->next) {
        if (p->data < minNode->data) {
            minNode = p;
            minPre = pre;
        }
        pre = p;
    }

    minValue = minNode->data;
    if (minPre == nullptr)
        L = L->next;
    else
        minPre->next = minNode->next;
    delete minNode;
    return true;
}

• 无头链表删除首元必须修改 L；本实现一趟完成，不需要先找值再二次查找。
• 时间 $O(n)$、空间 $O(1)$。

---

2.9 代码题 9：递增输出并销毁带头单链表

void PrintAscendingAndDestroy(LNode *&head, std::ostream &out) {
    while (head->next != nullptr) {
        LNode *minPre = head;
        for (LNode *pre = head; pre->next != nullptr; pre = pre->next)
            if (pre->next->data < minPre->next->data)
                minPre = pre;

        LNode *q = minPre->next;
        out << q->data << ' ';
        minPre->next = q->next;
        delete q;
    }
    delete head;
    head = nullptr;
}

• 每轮找出当前最小结点并删除；若有重复值，输出是非递减序列，而非严格递增。
• 总时间 $O(n^2)$、空间 $O(1)$；若只要求排序而不要求此过程，链表归并排序更高效。

---

2.10 代码题 10：按奇偶位置稳定拆分

将带头链表 A 拆成带头链表 A、B：A 保留原奇数位置结点，B 保留原偶数位置结点，二者相对次序不变。

LNode *SplitOddEvenStable(LNode *A) {
    LNode *B = new LNode{0, nullptr};
    LNode *tailA = A;
    LNode *tailB = B;
    LNode *p = A->next;
    A->next = nullptr;

    int position = 1;
    while (p != nullptr) {
        LNode *next = p->next;
        p->next = nullptr;
        if (position % 2 == 1) {
            tailA->next = p;
            tailA = p;
        } else {
            tailB->next = p;
            tailB = p;
        }
        p = next;
        ++position;
    }
    return B;
}

• 两表都用尾插，所以分别保持原相对次序。
• 原 PDF 写成 new LNode*，得到的是“指针对象”而不是结点；正确写法是 new LNode{...}。
• 时间 $O(n)$；除新头结点外额外空间 $O(1)$。

---

2.11 代码题 11：拆成正序奇位链与逆序偶位链

输入为 $(a_1,b_1,a_2,b_2,\ldots)$，输出 A=(a_1,a_2,...) 与 B=(...,b_2,b_1)。

LNode *SplitOddForwardEvenReverse(LNode *A) {
    LNode *B = new LNode{0, nullptr};
    LNode *tailA = A;
    LNode *p = A->next;
    A->next = nullptr;

    int position = 1;
    while (p != nullptr) {
        LNode *next = p->next;
        if (position % 2 == 1) {
            p->next = nullptr;
            tailA->next = p;      // 奇数位置尾插
            tailA = p;
        } else {
            p->next = B->next;    // 偶数位置头插
            B->next = p;
        }
        p = next;
        ++position;
    }
    return B;
}

• 奇数个输入结点时，最后一个结点自然留在 A。
• 时间 $O(n)$；除新头结点外额外空间 $O(1)$。

---

2.12 代码题 12：递增链表原地去重

void DeleteDuplicatesSorted(LNode *head) {
    LNode *p = head->next;
    while (p != nullptr && p->next != nullptr) {
        if (p->data == p->next->data) {
            LNode *q = p->next;
            p->next = q->next;
            delete q;
        } else {
            p = p->next;
        }
    }
}

• 删除后 p 不动，继续检查新后继；有序性保证重复值相邻。
• 时间 $O(n)$、空间 $O(1)$。

---

2.13 代码题 13：合并为非递减链表

复用两表原结点，结果存入 A；B 的头结点释放并置空。

void MergeIncreasing(LNode *&A, LNode *&B) {
    LNode *pa = A->next;
    LNode *pb = B->next;
    LNode *tail = A;

    while (pa != nullptr && pb != nullptr) {
        if (pa->data <= pb->data) {
            tail->next = pa;
            pa = pa->next;
        } else {
            tail->next = pb;
            pb = pb->next;
        }
        tail = tail->next;
    }
    tail->next = (pa != nullptr) ? pa : pb;

    delete B;
    B = nullptr;
}

• 相等时先取 A 可保持稳定性；时间 $O(m+n)$、空间 $O(1)$。

---

2.14 代码题 14：合并为非递增链表

每次取两表当前较小结点并头插到 A，从而把非递减选取次序反转为非递增。

void MergeDecreasing(LNode *&A, LNode *&B) {
    LNode *pa = A->next;
    LNode *pb = B->next;
    A->next = nullptr;

    while (pa != nullptr || pb != nullptr) {
        LNode *q;
        if (pb == nullptr ||
            (pa != nullptr && pa->data <= pb->data)) {
            q = pa;
            pa = pa->next;
        } else {
            q = pb;
            pb = pb->next;
        }
        q->next = A->next;
        A->next = q;
    }

    delete B;
    B = nullptr;
}

• 时间 $O(m+n)$、空间 $O(1)$；头插会反转相等记录的先后次序，因此本实现不稳定。

---

2.15 代码题 15：公共元素生成新链 C

A、B 均按非递减次序排列且不得破坏；以下按集合交集处理，每个公共值只在 C 中出现一次。

LNode *CommonValuesNewList(const LNode *A, const LNode *B) {
    LNode *C = new LNode{0, nullptr};
    LNode *tail = C;
    const LNode *pa = A->next;
    const LNode *pb = B->next;

    while (pa != nullptr && pb != nullptr) {
        if (pa->data < pb->data) {
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pb = pb->next;
        } else {
            ElemType value = pa->data;
            tail->next = new LNode{value, nullptr};
            tail = tail->next;
            while (pa != nullptr && pa->data == value) pa = pa->next;
            while (pb != nullptr && pb->data == value) pb = pb->next;
        }
    }
    return C;
}

• 时间 $O(m+n)$；新链空间 $O(k)$，$k$ 为不同公共值个数。
• 若题目把重复记录按多重集处理，则相等时各前进一步即可，输出次数为两侧重复次数的较小者。

---

2.16 代码题 16：公共元素原地保存在 A

以下假设两表内部无重复值。复用 A 中公共结点，释放其余 A 结点、全部 B 数据结点和 B 头结点。

void IntersectInPlace(LNode *&A, LNode *&B) {
    LNode *pa = A->next;
    LNode *pb = B->next;
    LNode *tail = A;
    A->next = nullptr;

    while (pa != nullptr && pb != nullptr) {
        if (pa->data == pb->data) {
            LNode *keep = pa;
            pa = pa->next;

            LNode *discardB = pb;
            pb = pb->next;
            delete discardB;

            keep->next = nullptr;
            tail->next = keep;
            tail = keep;
        } else if (pa->data < pb->data) {
            LNode *q = pa;
            pa = pa->next;
            delete q;
        } else {
            LNode *q = pb;
            pb = pb->next;
            delete q;
        }
    }

    while (pa != nullptr) {
        LNode *q = pa;
        pa = pa->next;
        delete q;
    }
    while (pb != nullptr) {
        LNode *q = pb;
        pb = pb->next;
        delete q;
    }
    delete B;
    B = nullptr;
}

• 时间 $O(m+n)$、空间 $O(1)$；释放前必须先保存后继。

---

2.17 代码题 17：判断 B 是否为 A 的连续子序列

bool IsContiguousSubsequence(const LNode *A, const LNode *B) {
    const LNode *pattern = B->next;
    if (pattern == nullptr) return true;

    for (const LNode *start = A->next;
         start != nullptr; start = start->next) {
        const LNode *pa = start;
        const LNode *pb = pattern;
        while (pa != nullptr && pb != nullptr &&
               pa->data == pb->data) {
            pa = pa->next;
            pb = pb->next;
        }
        if (pb == nullptr) return true;
    }
    return false;
}

• 空序列是任意序列的连续子序列；朴素匹配最坏时间 $O(mn)$、空间 $O(1)$。
• 原 PDF 的回退指针变量不一致，并在 pb 可能为空时继续解引用；上面用逐起点匹配消除该错误。

---

2.18 代码题 18：查找倒数第 k 个结点

bool KthFromEnd(const LNode *head, int k, ElemType &value) {
    if (k <= 0) return false;

    const LNode *fast = head->next;
    const LNode *slow = head->next;
    for (int i = 0; i < k; ++i) {
        if (fast == nullptr) return false;
        fast = fast->next;
    }

    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    value = slow->data;
    return true;
}

• fast 先走恰好 $k$ 步；链长等于 $k$ 时，slow 正好停在首元。
• 时间 $O(n)$、空间 $O(1)$。

---

2.19 代码题 19：按绝对值去重，保留首次出现

已知共有 $m$ 个结点且 $|data|\le n$，用大小为 $n+1$ 的标记数组记录某绝对值是否出现。

void DeleteDuplicateAbs(LNode *head, int n) {
    if (n < 0) return;
    bool *seen = new bool[n + 1]{};

    LNode *pre = head;
    while (pre->next != nullptr) {
        int value = pre->next->data;
        int index = (value < 0) ? -value : value;
        if (!seen[index]) {
            seen[index] = true;
            pre = pre->next;
        } else {
            LNode *q = pre->next;
            pre->next = q->next;
            delete q;
        }
    }
    delete[] seen;
}

• 时间 $O(m+n)$（含标记数组初始化）、空间 $O(n)$。
• 标记范围包含 0，所以数组长度必须为 $n+1$；源 PDF 的前驱指针未初始化且释放方式错误。

---

2.20 代码题 20：判断循环双链表是否对称

带头结点循环双链表满足空表 head->next==head->prior==head。

bool IsSymmetric(const DNode *head) {
    const DNode *left = head->next;
    const DNode *right = head->prior;

    while (left != right && left->prior != right) {
        if (left->data != right->data) return false;
        left = left->next;
        right = right->prior;
    }
    return true;
}

• left==right 表示奇数长度在中点相遇；left->prior==right 表示偶数长度已经交错。
• 右指针必须沿 prior 前移；原 PDF 错写成 q=q->next。
• 时间 $O(n)$、空间 $O(1)$。

---

2.21 代码题 21：连接两个带头循环单链表

拼接后只保留 h1 作为头结点，释放 h2 的头结点。

void ConcatCircular(LNode *h1, LNode *&h2) {
    if (h2 == nullptr) return;

    LNode *tail1 = h1;
    while (tail1->next != h1) tail1 = tail1->next;

    if (h2->next == h2) { // 第二表为空
        delete h2;
        h2 = nullptr;
        return;
    }

    LNode *tail2 = h2;
    while (tail2->next != h2) tail2 = tail2->next;

    tail1->next = h2->next;
    tail2->next = h1;
    delete h2;
    h2 = nullptr;
}

• 第一表为空时 tail1==h1，上述连接仍成立。
• 不能把 tail1->next 直接设为 h2 后保留两个头结点，否则第二个哨兵会混入数据链。
• 时间 $O(m+n)$、空间 $O(1)$。

---

2.22 代码题 22：循环单链表递增输出并销毁

void PrintCircularAscendingAndDestroy(LNode *&head,
                                      std::ostream &out) {
    while (head->next != head) {
        LNode *minPre = head;
        for (LNode *pre = head; pre->next != head; pre = pre->next)
            if (pre->next->data < minPre->next->data)
                minPre = pre;

        LNode *q = minPre->next;
        out << q->data << ' ';
        minPre->next = q->next;
        delete q;
    }
    delete head;
    head = nullptr;
}

• 循环终点是 head 而非 nullptr；重复值允许出现，输出为非递减序列。总时间 $O(n^2)$、空间 $O(1)$。
• 原 PDF 输出处混用了 min 与 minP，会解引用错误对象。

---

2.23 代码题 23：判断单链表是否有环

bool HasCycle(const LNode *first) {
    const LNode *slow = first;
    const LNode *fast = first;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

• 快指针到空说明无环；快慢指针相遇说明有环。
• 时间 $O(n)$、空间 $O(1)$。
• 原 PDF 的循环条件始终检查固定头指针 l，不能保护移动后的 fast->next，可能空指针解引用。

---

2.24 代码题 24：重排为 a1,an,a2,a(n-1),…

带头单链表先从中间断开，逆置后半段，再把两段交替连接。

void ReorderEnds(LNode *head) {
    if (head->next == nullptr || head->next->next == nullptr) return;

    LNode *slow = head->next;
    LNode *fast = head->next;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    LNode *second = slow->next;
    slow->next = nullptr;

    LNode *reversed = nullptr;
    while (second != nullptr) {
        LNode *next = second->next;
        second->next = reversed;
        reversed = second;
        second = next;
    }

    LNode *first = head->next;
    second = reversed;
    while (second != nullptr) {
        LNode *nextFirst = first->next;
        LNode *nextSecond = second->next;
        first->next = second;
        second->next = nextFirst;
        first = nextFirst;
        second = nextSecond;
    }
}

• 前半段长度为 $\lceil n/2\rceil$，后半段为 $\lfloor n/2\rfloor$，因此交替连接时 first 不会先为空。
• 时间 $O(n)$、空间 $O(1)$；每次改链前先保存两侧后继，避免丢链或成环。

---

2.25 原 PDF 关键错误清单

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：顺序表代码 · 下一篇：栈与队列代码
• 关联专题：链表原理

2.26 本节复盘

• 无头链表删除首元必须修改链表指针；带头链表通常统一检查 pre->next。
• 删除保存前驱，逆置保存后继，合并保存输入链当前入口；释放后不得再解引用。
• 有序链表的合并、交集与去重依赖单调性，可在线性时间完成。
• 倒数第 $k$ 个、找中点和判环使用快慢指针，但起点、先走步数和终止条件必须与头结点约定一致。
• 循环链表以头结点而非 nullptr 为终点；循环双链表的反向遍历必须使用 prior。
• 要求保留原链时新建结果结点；允许破坏输入时优先复用原结点，并明确释放弃用头结点。