第 1 章链表 · 数据结构与算法（1/12）

🎯 本章你会学到：链表的内存结构与它和数组的本质差别；C / C++ / Java / Python 四门语言各自的标准库写法与手写底层实现；反转、判环、找中点、合并四条有序链表这四个面试高频动作；以及一套能直接跑起来的验证方式。

这一章是「数据结构与算法」线的第一站。规则先说清楚：每个结构都给两版代码——先用语言自带的标准库把功能跑通，再手写一遍底层实现。只学标准库，面试手写题会卡住；只学手写，工程里会重复造轮子。

本章所有代码都在 gcc 16.1 / g++ 16.1 / javac 21 / Python 3.14 下实测编译运行通过，四份手写实现的输出逐字节一致，可以对照着横向看。

1.1 链表是什么：一串不连续的结点

数组把元素摆在一整块连续内存里，所以「第 5 个元素」可以直接算地址跳过去（随机访问 O(1)）；代价是中间插入或删除一个元素，后面的元素得整体搬家（O(n)）。

链表反过来：每个元素单独申请一小块内存，成为「结点」，结点里存两样东西——数据本身和指向下一个结点的指针。它们之间用指针串起来，内存上并不连续。

这样一来：插入和删除只要改几个指针（O(1)），但想找「第 5 个元素」只能从头一个一个数过去（O(n)）。这就是链表和数组最本质的取舍。

链表 vs 数组：一张表说清

对比项	数组	链表
内存布局	连续	分散，靠指针串联
随机访问第 k 个	O(1)	O(k)，要一个个走
已知位置插入/删除	O(n)，要搬后面的元素	O(1)，只改指针
查找某个值	无序 O(n)；有序可二分 O(log n)	只能 O(n)
额外空间	无	每个结点多存一个指针
缓存友好度	好（连续内存）	差（跳着访问）
手写难度	低	高，边界多（空表、头结点、尾结点）

📌 一句话判断用哪个：要频繁按下标读 → 数组；要频繁在中间插入删除、且已经拿到了位置 → 链表。真实工程里数组（动态数组、vector、ArrayList）用得远比链表多，链表主要在「结构本身要频繁增删」和「面试手写题」两个场景出场。

1.2 复杂度速查

操作	时间	空间	说明
头插	O(1)	O(1)	新结点的 next 指向原表头
尾插	O(n)	O(1)	单链表要先走到尾；带尾指针可降到 O(1)
查找某值	O(n)	O(1)	只能顺序扫描
删除某值	O(n)	O(1)	单链表要重新找前驱；双链表已知结点则 O(1)
反转	O(n)	O(1)	三指针迭代；递归写法空间 O(n)
找中点	O(n)	O(1)	快慢指针，快走两步慢走一步
判环	O(n)	O(1)	Floyd 快慢指针，相遇即有环
合并两条有序链表	O(n+m)	O(1)	双指针穿针引线；也可递归但空间 O(n+m)

1.3 先看标准库：四门语言各用什么

语言	标准库里的链表	特点
C	没有	C 标准库不提供链表容器，只能自己用结构体 + 指针写（见 1.4）
C++	`std::list` / `std::forward_list`	`forward_list` 是单链表，但没有 `size()`、没有 `push_back`；常用的是双向的 `std::list`
Java	`java.util.LinkedList`	双向链表，实现了 List 与 Deque 两个接口
Python	`collections.deque`	没有内置链表；`list` 是动态数组，要按链表用就用 `deque`

下面三段代码做的是同一件事：建表、尾插、查找、删除、反转、合并两条有序链表、按索引取第 2 个。三段输出完全一致。

C++：std::list

std_cpp.cpp

// =====================================================================
// 数据结构与算法 · 第 1 章 链表 · 标准库写法（C++ / std::list）
// 编译运行： g++ -std=c++17 -Wall -Wextra -Wpedantic -o app std_cpp.cpp && ./app
//
// 复杂度速查（时间 / 空间）
//   头插 push_front O(1) / O(1)     尾插 push_back O(1) / O(1)
//   查找 std::find O(n) / O(1)      删除 remove O(n) / O(1)
//   反转 reverse O(n) / O(1)        合并 merge O(n+m) / O(1)
//   按索引取第 k 个 O(k) / O(1)     ← 链表没有随机访问，这是它和数组最大的区别
// 说明：C++ 标准库的单链表是 std::forward_list（没有 size()、没有 push_back），
//      这里用 std::list（双向链表）演示同样的操作，接口更完整。
// =====================================================================

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <string>

void print_all(const std::string &prefix, const std::list<int> &l) {
    std::cout << prefix << ":";
    for (int v : l) {
        std::cout << " " << v;
    }
    std::cout << "\n";
}

int main() {
    std::list<int> l;

    l.push_front(3);
    l.push_front(2);
    l.push_front(1);
    print_all("[标准库] 头插 3,2,1", l);

    l.push_back(4);
    print_all("[标准库] 尾插 4", l);

    std::cout << "[标准库] 查找 3: "
              << (std::find(l.begin(), l.end(), 3) != l.end() ? "找到" : "未找到") << "\n";
    std::cout << "[标准库] 查找 9: "
              << (std::find(l.begin(), l.end(), 9) != l.end() ? "找到" : "未找到") << "\n";

    l.remove(2);
    print_all("[标准库] 删除 2", l);

    l.reverse();
    print_all("[标准库] 反转", l);

    std::cout << "[标准库] 长度: " << l.size() << "\n";

    std::list<int> a{1, 3, 5};
    std::list<int> b{2, 4, 6};
    a.merge(b);                              // 两条有序链表合并，O(n+m)
    print_all("[标准库] 合并两条有序链表", a);

    std::list<int>::iterator p = l.begin();
    std::advance(p, 1);                      // 链表要一个一个走，O(k)
    std::cout << "[标准库] 按索引取第 2 个: " << *p << "\n";
    return 0;
}

Java：java.util.LinkedList

LinkedListStd.java

// =====================================================================
// 数据结构与算法 · 第 1 章 链表 · 标准库写法（Java / java.util.LinkedList）
// 编译运行： javac -encoding UTF-8 LinkedListStd.java
//            java -Dstdout.encoding=UTF-8 LinkedListStd
//
// 复杂度速查（时间 / 空间）
//   头插 addFirst O(1) / O(1)       尾插 addLast O(1) / O(1)
//   查找 contains O(n) / O(1)       删除 remove(Object) O(n) / O(1)
//   反转 Collections.reverse O(n) / O(1)
//   按索引取第 k 个 get(k) O(k) / O(1)   ← 链表没有随机访问
//   合并两条有序链表（双指针遍历） O(n+m) / O(n+m)
// 陷阱：l.remove(2) 删的是下标 2 的元素（List 接口的 remove(int)），
//      要按值删除必须写成 l.remove(Integer.valueOf(2))。
// =====================================================================

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class LinkedListStd {

    static void printAll(String prefix, LinkedList<Integer> l) {
        StringBuilder sb = new StringBuilder(prefix).append(":");
        for (int v : l) {
            sb.append(" ").append(v);
        }
        System.out.println(sb);
    }

    static LinkedList<Integer> mergeSorted(LinkedList<Integer> a, LinkedList<Integer> b) {
        LinkedList<Integer> out = new LinkedList<>();
        Iterator<Integer> ia = a.iterator();
        Iterator<Integer> ib = b.iterator();
        Integer x = ia.hasNext() ? ia.next() : null;
        Integer y = ib.hasNext() ? ib.next() : null;
        while (x != null && y != null) {
            if (x <= y) {
                out.addLast(x);
                x = ia.hasNext() ? ia.next() : null;
            } else {
                out.addLast(y);
                y = ib.hasNext() ? ib.next() : null;
            }
        }
        while (x != null) { out.addLast(x); x = ia.hasNext() ? ia.next() : null; }
        while (y != null) { out.addLast(y); y = ib.hasNext() ? ib.next() : null; }
        return out;
    }

    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<>();

        l.addFirst(3);
        l.addFirst(2);
        l.addFirst(1);
        printAll("[标准库] 头插 3,2,1", l);

        l.addLast(4);
        printAll("[标准库] 尾插 4", l);

        System.out.println("[标准库] 查找 3: " + (l.contains(3) ? "找到" : "未找到"));
        System.out.println("[标准库] 查找 9: " + (l.contains(9) ? "找到" : "未找到"));

        l.remove(Integer.valueOf(2));
        printAll("[标准库] 删除 2", l);

        Collections.reverse(l);
        printAll("[标准库] 反转", l);

        System.out.println("[标准库] 长度: " + l.size());

        LinkedList<Integer> a = new LinkedList<>(List.of(1, 3, 5));
        LinkedList<Integer> b = new LinkedList<>(List.of(2, 4, 6));
        printAll("[标准库] 合并两条有序链表", mergeSorted(a, b));

        System.out.println("[标准库] 按索引取第 2 个: " + l.get(1));
    }
}

Python：collections.deque

std_python.py

# =====================================================================
# 数据结构与算法 · 第 1 章 链表 · 标准库写法（Python / collections.deque）
# 运行： python std_python.py
#
# 复杂度速查（时间 / 空间）
#   头插 appendleft O(1) / O(1)     尾插 append O(1) / O(1)
#   查找 in O(n) / O(1)             删除 remove O(n) / O(1)
#   反转 reverse O(n) / O(1)        合并两条有序链表 O(n+m) / O(n+m)
#   按索引取第 k 个 d[k] O(k) / O(1)   ← 链表没有随机访问
# 说明：Python 没有内置链表。list 是动态数组，索引访问是 O(1)；
#      要按链表方式用，应该用 collections.deque（两端插入删除都是 O(1)），
#      它的索引访问是 O(n)，正好能体现链表"查得慢、插得快"的特点。
# =====================================================================

from collections import deque


def print_all(prefix, d):
    print(prefix + ": " + " ".join(str(v) for v in d))


def merge_sorted(a, b):
    """两条有序链表合并：每次取更小的那个队头，O(n+m)"""
    a = deque(a)
    b = deque(b)
    out = deque()
    while a and b:
        if a[0] <= b[0]:
            out.append(a.popleft())
        else:
            out.append(b.popleft())
    out.extend(a)
    out.extend(b)
    return out


def main():
    d = deque()

    d.appendleft(3)
    d.appendleft(2)
    d.appendleft(1)
    print_all("[标准库] 头插 3,2,1", d)

    d.append(4)
    print_all("[标准库] 尾插 4", d)

    print("[标准库] 查找 3: %s" % ("找到" if 3 in d else "未找到"))
    print("[标准库] 查找 9: %s" % ("找到" if 9 in d else "未找到"))

    d.remove(2)
    print_all("[标准库] 删除 2", d)

    d.reverse()
    print_all("[标准库] 反转", d)

    print("[标准库] 长度: %d" % len(d))

    print_all("[标准库] 合并两条有序链表", merge_sorted(deque([1, 3, 5]), deque([2, 4, 6])))

    print("[标准库] 按索引取第 2 个: %d" % d[1])


if __name__ == "__main__":
    main()

三段代码的实测输出

运行结果（三份输出逐字节一致）

[标准库] 头插 3,2,1: 1 2 3
[标准库] 尾插 4: 1 2 3 4
[标准库] 查找 3: 找到
[标准库] 查找 9: 未找到
[标准库] 删除 2: 1 3 4
[标准库] 反转: 4 3 1
[标准库] 长度: 3
[标准库] 合并两条有序链表: 1 2 3 4 5 6
[标准库] 按索引取第 2 个: 3

⚠️ 两个真会踩的坑：
① Java 里 list.remove(2) 删的是下标 2 的元素，不是值为 2 的元素——List 接口重载了 remove(int)。要按值删必须写 list.remove(Integer.valueOf(2))。
② C++ 的 std::forward_list 是单链表，没有 size() 也没有 push_back，需要自己维护计数；图省事就用 std::list，但它多存一个前驱指针。

1.4 再手写一遍：四门语言的底层实现

标准库会用只是第一步。手写链表练的是三件事：指针/引用怎么接、边界怎么判、内存谁负责释放。面试手写题基本都在这个层面。

下面四份代码是同一份逻辑的四种写法：函数名、变量名、打印格式全部对齐，连输出都逐字节一致，方便你横向对比语法差异。

C：结构体 + malloc/free

raw_c.c

/* =====================================================================
   数据结构与算法 · 第 1 章 链表 · 手写实现（C）
   编译运行： gcc -std=c17 -Wall -Wextra -o app raw_c.c && ./app

   复杂度速查（时间 / 空间）
     头插 O(1) / O(1)          尾插 O(n) / O(1)
     查找 O(n) / O(1)          删除 O(n) / O(1)    （单链表要重新找前驱）
     反转 O(n) / O(1)          找中点 O(n) / O(1)
     判环 O(n) / O(1)          合并两条有序链表 O(n+m) / O(1)
   说明：C 没有标准库链表，用结构体 + malloc/free 自己组织内存，
        这正是"指针实现"在 C 里的标准写法。
   ===================================================================== */

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

/* 头插：新结点接到表头，O(1) */
static Node *push_front(Node *head, int value) {
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) return head;
    node->value = value;
    node->next = head;
    return node;
}

/* 尾插：先走到最后一个结点，O(n) */
static Node *push_back(Node *head, int value) {
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) return head;
    node->value = value;
    node->next = NULL;
    if (head == NULL) return node;
    Node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = node;
    return head;
}

/* 遍历打印：以 "prefix: 1 2 3" 的形式输出 */
static void print_all(const char *prefix, Node *head) {
    printf("%s:", prefix);
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        printf(" %d", cur->value);
    }
    printf("\n");
}

/* 查找：返回第几个（从 1 开始），找不到返回 0，O(n) */
static int index_of(Node *head, int value) {
    int i = 1;
    for (Node *cur = head; cur != NULL; cur = cur->next, i++) {
        if (cur->value == value) return i;
    }
    return 0;
}

/* 删除第一个匹配的结点，O(n) */
static Node *erase(Node *head, int value) {
    Node *prev = NULL;
    Node *cur = head;
    while (cur != NULL) {
        if (cur->value == value) {
            if (prev == NULL) {
                head = cur->next;
            } else {
                prev->next = cur->next;
            }
            free(cur);
            return head;
        }
        prev = cur;
        cur = cur->next;
    }
    return head;
}

/* 反转：三指针迭代，O(n) 时间、O(1) 空间 */
static Node *reverse(Node *head) {
    Node *prev = NULL;
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

/* 找中点：快慢指针，快指针走两步、慢指针走一步，O(n) */
static Node *middle(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

/* 判环：Floyd 快慢指针，相遇即有环，O(n) */
static int has_cycle(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

/* 长度：O(n) */
static int length(Node *head) {
    int n = 0;
    for (Node *cur = head; cur != NULL; cur = cur->next) n++;
    return n;
}

/* 合并两条有序链表：双指针穿针引线，O(n+m) */
static Node *merge_sorted(Node *a, Node *b) {
    Node dummy;
    dummy.next = NULL;
    Node *tail = &dummy;
    while (a != NULL && b != NULL) {
        if (a->value <= b->value) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;
    return dummy.next;
}

/* 整表释放：C 里必须自己做，否则内存泄漏 */
static void free_all(Node *head) {
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    Node *list = NULL;

    list = push_front(list, 3);
    list = push_front(list, 2);
    list = push_front(list, 1);
    print_all("[手写] 头插 3,2,1", list);

    list = push_back(list, 4);
    print_all("[手写] 尾插 4", list);

    int pos = index_of(list, 3);
    printf("[手写] 查找 3: 找到, 第 %d 个\n", pos);
    printf("[手写] 查找 9: %s\n", index_of(list, 9) == 0 ? "未找到" : "找到");

    list = erase(list, 2);
    print_all("[手写] 删除 2", list);

    list = reverse(list);
    print_all("[手写] 反转", list);

    printf("[手写] 找中点: %d\n", middle(list)->value);

    printf("[手写] 判环(无环): %s\n", has_cycle(list) ? "有环" : "无环");
    Node *last = list;
    while (last->next != NULL) last = last->next;
    last->next = list;                       /* 人为造一个环 */
    printf("[手写] 判环(有环): %s\n", has_cycle(list) ? "有环" : "无环");
    last->next = NULL;                       /* 拆掉环，否则释放会出错 */

    printf("[手写] 长度: %d\n", length(list));

    Node *a = NULL;
    Node *b = NULL;
    a = push_back(a, 1); a = push_back(a, 3); a = push_back(a, 5);
    b = push_back(b, 2); b = push_back(b, 4); b = push_back(b, 6);
    Node *merged = merge_sorted(a, b);
    print_all("[手写] 合并两条有序链表", merged);

    free_all(list);
    free_all(merged);
    return 0;
}

C++：new/delete 手写结点

raw_cpp.cpp

// =====================================================================
// 数据结构与算法 · 第 1 章 链表 · 手写实现（C++）
// 编译运行： g++ -std=c++17 -Wall -Wextra -Wpedantic -o app raw_cpp.cpp && ./app
//
// 复杂度速查（时间 / 空间）
//   头插 O(1) / O(1)          尾插 O(n) / O(1)
//   查找 O(n) / O(1)          删除 O(n) / O(1)    （单链表要重新找前驱）
//   反转 O(n) / O(1)          找中点 O(n) / O(1)
//   判环 O(n) / O(1)          合并两条有序链表 O(n+m) / O(1)
// 说明：这里用 new/delete 手写结点，和 C 版逻辑完全一致，便于横向对照；
//      用标准库的写法见同目录 std_cpp.cpp。
// =====================================================================

#include <iostream>

struct Node {
    int value;
    Node *next;
};

// 头插：新结点接到表头，O(1)
Node *push_front(Node *head, int value) {
    return new Node{value, head};
}

// 尾插：先走到最后一个结点，O(n)
Node *push_back(Node *head, int value) {
    Node *node = new Node{value, nullptr};
    if (head == nullptr) return node;
    Node *cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
    return head;
}

// 遍历打印：以 "prefix: 1 2 3" 的形式输出
void print_all(const std::string &prefix, Node *head) {
    std::cout << prefix << ":";
    for (Node *cur = head; cur != nullptr; cur = cur->next) {
        std::cout << " " << cur->value;
    }
    std::cout << "\n";
}

// 查找：返回第几个（从 1 开始），找不到返回 0，O(n)
int index_of(Node *head, int value) {
    int i = 1;
    for (Node *cur = head; cur != nullptr; cur = cur->next, ++i) {
        if (cur->value == value) return i;
    }
    return 0;
}

// 删除第一个匹配的结点，O(n)
Node *erase(Node *head, int value) {
    Node *prev = nullptr;
    Node *cur = head;
    while (cur != nullptr) {
        if (cur->value == value) {
            if (prev == nullptr) head = cur->next;
            else prev->next = cur->next;
            delete cur;
            return head;
        }
        prev = cur;
        cur = cur->next;
    }
    return head;
}

// 反转：三指针迭代，O(n) 时间、O(1) 空间
Node *reverse(Node *head) {
    Node *prev = nullptr;
    Node *cur = head;
    while (cur != nullptr) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// 找中点：快慢指针，O(n)
Node *middle(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 判环：Floyd 快慢指针，O(n)
bool has_cycle(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// 长度：O(n)
int length(Node *head) {
    int n = 0;
    for (Node *cur = head; cur != nullptr; cur = cur->next) ++n;
    return n;
}

// 合并两条有序链表：双指针穿针引线，O(n+m)
Node *merge_sorted(Node *a, Node *b) {
    Node dummy{0, nullptr};
    Node *tail = &dummy;
    while (a != nullptr && b != nullptr) {
        if (a->value <= b->value) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != nullptr) ? a : b;
    return dummy.next;
}

// 整表释放：手写 new 就要手写 delete
void free_all(Node *head) {
    while (head != nullptr) {
        Node *next = head->next;
        delete head;
        head = next;
    }
}

int main() {
    Node *list = nullptr;

    list = push_front(list, 3);
    list = push_front(list, 2);
    list = push_front(list, 1);
    print_all("[手写] 头插 3,2,1", list);

    list = push_back(list, 4);
    print_all("[手写] 尾插 4", list);

    int pos = index_of(list, 3);
    std::cout << "[手写] 查找 3: 找到, 第 " << pos << " 个\n";
    std::cout << "[手写] 查找 9: " << (index_of(list, 9) == 0 ? "未找到" : "找到") << "\n";

    list = erase(list, 2);
    print_all("[手写] 删除 2", list);

    list = reverse(list);
    print_all("[手写] 反转", list);

    std::cout << "[手写] 找中点: " << middle(list)->value << "\n";

    std::cout << "[手写] 判环(无环): " << (has_cycle(list) ? "有环" : "无环") << "\n";
    Node *last = list;
    while (last->next != nullptr) last = last->next;
    last->next = list;                        // 人为造一个环
    std::cout << "[手写] 判环(有环): " << (has_cycle(list) ? "有环" : "无环") << "\n";
    last->next = nullptr;                     // 拆掉环，否则释放会出错

    std::cout << "[手写] 长度: " << length(list) << "\n";

    Node *a = nullptr;
    Node *b = nullptr;
    a = push_back(a, 1); a = push_back(a, 3); a = push_back(a, 5);
    b = push_back(b, 2); b = push_back(b, 4); b = push_back(b, 6);
    Node *merged = merge_sorted(a, b);
    print_all("[手写] 合并两条有序链表", merged);

    free_all(list);
    free_all(merged);
    return 0;
}

Java：类 + 对象引用

LinkedListRaw.java

// =====================================================================
// 数据结构与算法 · 第 1 章 链表 · 手写实现（Java）
// 编译运行： javac -encoding UTF-8 LinkedListRaw.java
//            java -Dstdout.encoding=UTF-8 LinkedListRaw
//
// 复杂度速查（时间 / 空间）
//   头插 O(1) / O(1)          尾插 O(n) / O(1)
//   查找 O(n) / O(1)          删除 O(n) / O(1)    （单链表要重新找前驱）
//   反转 O(n) / O(1)          找中点 O(n) / O(1)
//   判环 O(n) / O(1)          合并两条有序链表 O(n+m) / O(1)
// 说明：Java 手写链表不需要 free —— 对象没有引用后由 GC 回收，
//      这一点和 C / C++ 的手写实现正好形成对照。
// =====================================================================

public class LinkedListRaw {

    static class Node {
        int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    // 头插：新结点接到表头，O(1)
    static Node pushFront(Node head, int value) {
        return new Node(value, head);
    }

    // 尾插：先走到最后一个结点，O(n)
    static Node pushBack(Node head, int value) {
        Node node = new Node(value, null);
        if (head == null) return node;
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = node;
        return head;
    }

    // 遍历打印：以 "prefix: 1 2 3" 的形式输出
    static void printAll(String prefix, Node head) {
        StringBuilder sb = new StringBuilder(prefix).append(":");
        for (Node cur = head; cur != null; cur = cur.next) {
            sb.append(" ").append(cur.value);
        }
        System.out.println(sb);
    }

    // 查找：返回第几个（从 1 开始），找不到返回 0，O(n)
    static int indexOf(Node head, int value) {
        int i = 1;
        for (Node cur = head; cur != null; cur = cur.next, ++i) {
            if (cur.value == value) return i;
        }
        return 0;
    }

    // 删除第一个匹配的结点，O(n)
    static Node erase(Node head, int value) {
        Node prev = null;
        Node cur = head;
        while (cur != null) {
            if (cur.value == value) {
                if (prev == null) head = cur.next;
                else prev.next = cur.next;
                return head;
            }
            prev = cur;
            cur = cur.next;
        }
        return head;
    }

    // 反转：三指针迭代，O(n) 时间、O(1) 空间
    static Node reverse(Node head) {
        Node prev = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // 找中点：快慢指针，O(n)
    static Node middle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 判环：Floyd 快慢指针，O(n)
    static boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    // 长度：O(n)
    static int length(Node head) {
        int n = 0;
        for (Node cur = head; cur != null; cur = cur.next) ++n;
        return n;
    }

    // 合并两条有序链表：双指针穿针引线，O(n+m)
    static Node mergeSorted(Node a, Node b) {
        Node dummy = new Node(0, null);
        Node tail = dummy;
        while (a != null && b != null) {
            if (a.value <= b.value) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }

    public static void main(String[] args) {
        Node list = null;

        list = pushFront(list, 3);
        list = pushFront(list, 2);
        list = pushFront(list, 1);
        printAll("[手写] 头插 3,2,1", list);

        list = pushBack(list, 4);
        printAll("[手写] 尾插 4", list);

        int pos = indexOf(list, 3);
        System.out.println("[手写] 查找 3: 找到, 第 " + pos + " 个");
        System.out.println("[手写] 查找 9: " + (indexOf(list, 9) == 0 ? "未找到" : "找到"));

        list = erase(list, 2);
        printAll("[手写] 删除 2", list);

        list = reverse(list);
        printAll("[手写] 反转", list);

        System.out.println("[手写] 找中点: " + middle(list).value);

        System.out.println("[手写] 判环(无环): " + (hasCycle(list) ? "有环" : "无环"));
        Node last = list;
        while (last.next != null) last = last.next;
        last.next = list;                       // 人为造一个环
        System.out.println("[手写] 判环(有环): " + (hasCycle(list) ? "有环" : "无环"));
        last.next = null;                       // 拆掉环

        System.out.println("[手写] 长度: " + length(list));

        Node a = null;
        Node b = null;
        a = pushBack(a, 1); a = pushBack(a, 3); a = pushBack(a, 5);
        b = pushBack(b, 2); b = pushBack(b, 4); b = pushBack(b, 6);
        Node merged = mergeSorted(a, b);
        printAll("[手写] 合并两条有序链表", merged);
    }
}

Python：类 + 引用（用 slots 省内存）

raw_python.py

# =====================================================================
# 数据结构与算法 · 第 1 章 链表 · 手写实现（Python）
# 运行： python raw_python.py
#
# 复杂度速查（时间 / 空间）
#   头插 O(1) / O(1)          尾插 O(n) / O(1)
#   查找 O(n) / O(1)          删除 O(n) / O(1)    （单链表要重新找前驱）
#   反转 O(n) / O(1)          找中点 O(n) / O(1)
#   判环 O(n) / O(1)          合并两条有序链表 O(n+m) / O(1)
# 说明：Python 没有指针，这里用类 + 对象引用模拟结点，
#      逻辑与 C / C++ / Java 版完全一致，便于横向对照。
# =====================================================================


class Node:
    __slots__ = ("value", "next")

    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt


def push_front(head, value):
    """头插：新结点接到表头，O(1)"""
    return Node(value, head)


def push_back(head, value):
    """尾插：先走到最后一个结点，O(n)"""
    node = Node(value)
    if head is None:
        return node
    cur = head
    while cur.next is not None:
        cur = cur.next
    cur.next = node
    return head


def print_all(prefix, head):
    """遍历打印：以 "prefix: 1 2 3" 的形式输出"""
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.value))
        cur = cur.next
    print(prefix + ": " + " ".join(parts) if parts else prefix + ":")


def index_of(head, value):
    """查找：返回第几个（从 1 开始），找不到返回 0，O(n)"""
    i = 1
    cur = head
    while cur is not None:
        if cur.value == value:
            return i
        cur = cur.next
        i += 1
    return 0


def erase(head, value):
    """删除第一个匹配的结点，O(n)"""
    prev = None
    cur = head
    while cur is not None:
        if cur.value == value:
            if prev is None:
                return cur.next
            prev.next = cur.next
            return head
        prev = cur
        cur = cur.next
    return head


def reverse(head):
    """反转：三指针迭代，O(n) 时间、O(1) 空间"""
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def middle(head):
    """找中点：快慢指针，O(n)"""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow


def has_cycle(head):
    """判环：Floyd 快慢指针，O(n)"""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def length(head):
    """长度：O(n)"""
    n = 0
    cur = head
    while cur is not None:
        n += 1
        cur = cur.next
    return n


def merge_sorted(a, b):
    """合并两条有序链表：双指针穿针引线，O(n+m)"""
    dummy = Node(0)
    tail = dummy
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next


def main():
    lst = None

    lst = push_front(lst, 3)
    lst = push_front(lst, 2)
    lst = push_front(lst, 1)
    print_all("[手写] 头插 3,2,1", lst)

    lst = push_back(lst, 4)
    print_all("[手写] 尾插 4", lst)

    print("[手写] 查找 3: 找到, 第 %d 个" % index_of(lst, 3))
    print("[手写] 查找 9: %s" % ("未找到" if index_of(lst, 9) == 0 else "找到"))

    lst = erase(lst, 2)
    print_all("[手写] 删除 2", lst)

    lst = reverse(lst)
    print_all("[手写] 反转", lst)

    print("[手写] 找中点: %d" % middle(lst).value)

    print("[手写] 判环(无环): %s" % ("有环" if has_cycle(lst) else "无环"))
    last = lst
    while last.next is not None:
        last = last.next
    last.next = lst                          # 人为造一个环
    print("[手写] 判环(有环): %s" % ("有环" if has_cycle(lst) else "无环"))
    last.next = None                         # 拆掉环

    print("[手写] 长度: %d" % length(lst))

    a = None
    b = None
    a = push_back(a, 1); a = push_back(a, 3); a = push_back(a, 5)
    b = push_back(b, 2); b = push_back(b, 4); b = push_back(b, 6)
    merged = merge_sorted(a, b)
    print_all("[手写] 合并两条有序链表", merged)


if __name__ == "__main__":
    main()

四份代码的实测输出

运行结果（四份输出逐字节一致）

[手写] 头插 3,2,1: 1 2 3
[手写] 尾插 4: 1 2 3 4
[手写] 查找 3: 找到, 第 3 个
[手写] 查找 9: 未找到
[手写] 删除 2: 1 3 4
[手写] 反转: 4 3 1
[手写] 找中点: 3
[手写] 判环(无环): 无环
[手写] 判环(有环): 有环
[手写] 长度: 3
[手写] 合并两条有序链表: 1 2 3 4 5 6

🔍 横向对比时重点看这三处：
① 空指针怎么写：C/C++ 是 NULL / nullptr，Java 是 null，Python 是 None；
② 内存谁管：C 要 free、C++ 要 delete，Java 和 Python 交给 GC，所以它们的实现里没有释放循环；
③ 结点怎么定义：C 用 struct + 自身指针，C++ 用 struct + 聚合初始化，Java / Python 用类。

1.5 运行命令（照抄就能跑）

语言	文件	命令
C	raw_c.c	`gcc -std=c17 -Wall -Wextra -o app raw_c.c && ./app`
C++（手写）	raw_cpp.cpp	`g++ -std=c++17 -Wall -Wextra -Wpedantic -o app raw_cpp.cpp && ./app`
C++（标准库）	std_cpp.cpp	`g++ -std=c++17 -Wall -Wextra -Wpedantic -o app std_cpp.cpp && ./app`
Java（手写）	LinkedListRaw.java	`javac -encoding UTF-8 LinkedListRaw.java` 然后 `java -Dstdout.encoding=UTF-8 LinkedListRaw`
Java（标准库）	LinkedListStd.java	`javac -encoding UTF-8 LinkedListStd.java` 然后 `java -Dstdout.encoding=UTF-8 LinkedListStd`
Python（手写）	raw_python.py	`python raw_python.py`
Python（标准库）	std_python.py	`python std_python.py`

⚙️ Windows 终端中文乱码时：先执行 chcp 65001 切到 UTF-8；Python 还可以临时设环境变量 set PYTHONIOENCODING=utf-8，Java 用上面的 -Dstdout.encoding=UTF-8。macOS / Linux 把 ./app.exe 换成 ./app 即可。本章代码以 Windows PowerShell 为主验证。

1.6 面试高频四件套

下面四个动作，上面四份手写代码里都已经实现并跑通了。这里说清楚它们各自在考什么。

① 反转链表：三指针

核心是三个指针 prev / cur / next：先用 next 存住下一个结点（否则改指针后就找不到路了），再把 cur.next 指向 prev，然后三个指针整体往后挪一格。

写法	时间	空间	面试建议
迭代（三指针）	O(n)	O(1)	首选，能手写就要能手写这个
递归	O(n)	O(n) 递归栈	能讲清思路即可，链表长了会爆栈

最容易错的地方：循环条件写成 cur->next != nullptr（会漏掉最后一个结点）；或者忘记先保存 next，改完指针就断链了。

② 判环：Floyd 快慢指针

两个指针同时从表头出发，慢的每次走 1 步、快的每次走 2 步。如果链表有环，快指针一定会在环里追上慢指针；如果没有环，快指针会先走到 null。

复杂度 O(n) 时间、O(1) 空间。另一个常见解法是用哈希表存访问过的结点，时间一样但空间 O(n)——面试里要能说出为什么快慢指针更优。

延伸问法：怎么找入环点？两指针相遇后，把一个指针放回表头，两个指针都每次走 1 步，再次相遇的位置就是入环点。

③ 找中点：快慢指针

和判环同一套骨架，只是循环里不比较指针相等。偶数个结点时，快指针走完，慢指针停在后半段的第一个（本章实现就是这个行为：3 个结点返回第 2 个）。这个动作是「归并排序链表」「判断回文链表」「重排链表」的前置步骤。

④ 合并两条有序链表：双指针 + 哑结点

两条链表各一个指针，每次把较小的那个结点接到结果尾部，直到某一条走完，再接上剩下的整条。哑结点（dummy）是关键技巧：它让「结果表的第一个结点」不需要特殊处理，代码能短一大截。

复杂度 O(n+m) 时间。这是归并排序的基础动作，也是「合并 K 条有序链表」的原题。

1.7 易错点清单

易错点	后果	正确做法
反转前不保存 next	改指针后断链，后半段全丢	先 `next = cur.next`，再改 `cur.next`
删除头结点没单独处理	头指针没更新，删了等于没删	用哑结点，或判断 `prev == null`
C/C++ 忘了释放整表	内存泄漏	写一个 `free_all` / `freeList` 并在结尾调用
造了环没拆就释放	释放时死循环或崩溃	判环演示后立刻把尾部 `next` 置空
快指针判空顺序写反	`fast->next->next` 空指针解引用	先判 `fast != null && fast.next != null`
Java 用 `remove(2)` 想删值	删掉的是下标 2 的元素	`remove(Integer.valueOf(2))`
用 Python 的 list 当链表	中间插入删除是 O(n)，且名不副实	链表语义用 `collections.deque`；要随机访问就用 list，但那是数组

1.8 练习

1.1手写并按复杂度说清

不看上面的代码，用自己的话写出「删除单链表中值为 x 的第一个结点」的步骤，并说明为什么时间复杂度是 O(n) 而不是 O(1)。

提示：想清楚单链表你能不能「往回走」。

1.2改一处，比一比

把本章任一语言的手写实现里的「找中点」改成返回前一个结点（偶数个结点时返回前半段最后一个），跑一遍看输出变化。

提示：让快指针从 head.next 出发，或者用 slow 的前驱一路跟着走。

1.3判断回文链表

用「找中点 + 反转后半段 + 逐个比较」写一个函数判断链表是否回文，要求时间 O(n)、空间 O(1)。

提示：本章的「找中点」和「反转」拼起来就是答案；注意比较完要不要把后半段再转回去（工程上要，面试里说明即可）。

1.4找入环点

在判环的基础上，返回入环的那个结点（无环返回 null）。跑通本章的「有环」用例验证。

提示：相遇后把一个指针放回表头，两指针同速前进，再次相遇即入环点。

1.5合并 K 条有序链表（进阶）

用「优先队列」或「两两合并」把 K 条有序链表合并成一条，分析两种做法的时间复杂度。

提示：两两合并是 O(N log K)；优先队列是 O(N log K) 但常数不同，注意说清 N 是总结点数。

📚 本文概念都在知识大全：

链表 · 时间复杂度 · 动态内存 malloc/free · 指针 · STL · Java 集合框架 · Python 容器

一句话回顾：链表用指针把分散的结点串起来，换来 O(1) 的插入删除，代价是 O(n) 的查找；四门语言里只有 C++ / Java / Python 有现成的链表容器，C 必须自己写——而面试考的恰恰是那个「自己写」的部分。

1.1 链表是什么：一串不连续的结点

链表 vs 数组：一张表说清

1.2 复杂度速查

1.3 先看标准库：四门语言各用什么

C++：std::list

Java：java.util.LinkedList

Python：collections.deque

三段代码的实测输出

1.4 再手写一遍：四门语言的底层实现

C：结构体 + malloc/free

C++：new/delete 手写结点

Java：类 + 对象引用

Python：类 + 引用（用 __slots__ 省内存）

四份代码的实测输出

1.5 运行命令（照抄就能跑）

1.6 面试高频四件套

① 反转链表：三指针

② 判环：Floyd 快慢指针

③ 找中点：快慢指针

④ 合并两条有序链表：双指针 + 哑结点

1.7 易错点清单

1.8 练习

Python：类 + 引用（用 slots 省内存）