链表

单链表

定义：

class Node {
  public:
    int value;
    Node *next;
    Node() : value(0), next(nullptr) {}
    Node(int x) : value(x), next(nullptr) {}
    Node(int x, Node *next) : value(x), next(next) {}
};

尾插法

尾插法是将新节点添加到链表的末尾。

一般做法是使用一个尾指针指向链表的最后一个节点，然后将新节点插入到尾指针的后面，并更新尾指针。

Node *createListTail(std::vector<int> &arr) {
    Node dummy;
    Node *tail = &dummy;

    for (int x : arr) {
        tail->next = new Node{x, nullptr};
        tail = tail->next;
    }
    return dummy.next;
}

这里使用了一个哑节点 dummy，它的 next 指向链表的第一个节点。这样可以简化代码逻辑，避免处理空链表的特殊情况。

头插法

头插法是将新节点添加到链表的开头。

头插法先创建一个新节点，然后将其 next 指向当前链表的头节点，最后更新头节点为新节点。

Node *createListHead(std::vector<int> &arr) {
    Node *result = nullptr;
    for (auto x : arr) {
        result = new Node{x, result};
        /*
        展开：
        auto tmp = new Node(x);
        tmp->next = result;
        result = tmp;
        */
    }
    return result;
}

演示如下：

# 初始状态
head
|
3 -> 2 -> 1 -> nullptr

# 创建新节点
  head
   |
4  3 -> 2 -> 1 -> nullptr
|
nullptr

# 设置next

    head
     |
4 -> 3 -> 2 -> 1 -> nullptr

# 更新头指针
head
|
4 -> 3 -> 2 -> 1 -> nullptr

反转链表

示例题目：反转链表

更多解法看反转链表。

学会了头插法，反转链表就很简单了。

/*
遍历旧链表，使用头插法创建新链表。
时间复杂度 O(n)，空间复杂度 O(n)。
*/
Node *reverseList(Node *head) {
    Node *curr = nullptr;

    while (head != nullptr) {
        curr = new Node(head->value, curr);
        head = head->next;
    }
    return curr;
}

同时也可以原地操作，不新建节点，还是头插法：

Node *reverseList(Node *head) {
    Node *curr = nullptr;

    while (head != nullptr) {
        // 需要操作的节点
        auto ptr = head;
        // 旧链表转移到下一个节点
        head = head->next;
        // 头插法， 省去了创建节点的步骤，只需更新next和头指针即可。
        ptr->next = curr;
        curr = ptr;
    }
    return curr; // 返回新的头节点
}

插入节点

在一个节点后插入新节点。分为以下步骤：

1. 创建新节点。
2. 将新节点的 next 指向当前节点的 next。
3. 将当前节点的 next 指向新节点。

void insertNode(Node *prev, int value) {
    if (prev == nullptr) {
        return; // 或者抛出异常
    }
    prev->next = new Node{value, prev->next};
    /*
    展开：
    auto newNode = new Node(value);
    newNode->next = prev->next;
    prev->next = newNode;
    */
}

删除节点

删除节点分为以下步骤：

1. 找到要删除的节点。
2. 将前一个节点的 next 指向要删除节点的 next
3. 释放要删除的节点。

void deleteNode(Node *prev) {
    if (prev == nullptr || prev->next == nullptr) {
        return; // 或者抛出异常
    }
    Node *toDelete = prev->next;
    prev->next = toDelete->next;
    delete toDelete;
}

还有一种常见的删除节点方法是直接删除当前节点，这种方法需要将当前节点的值替换为下一个节点的值，然后删除下一个节点。

缺点是这种方法不能删除链表的最后一个节点。

因为我们没有办法获取到前一个节点，就没办法更新前一个节点的 next 指针为 nullptr。

void deleteCurrentNode(Node *curr) {
    if (curr == nullptr || curr->next == nullptr) {
        return; // 或者抛出异常
    }
    // 找到下一个节点
    auto p = curr->next;
    // 将当前节点的值替换为下一个节点的值
    curr->next = p->next;
    curr->value = p->value;
    // 删除下一个节点
    delete p;
}