《剑指Offer》第2章笔记 链表

链表应该是面试时被提及最频繁的数据结构。

链表的结构很简单，它由指针把若干个节点连接成链状结构，链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现，代码量比较适合面试（哈希表、有向图等复杂的一个操作可能就需要很多代码）。

链表是一种动态数据结构，创建链表时，无须知道链表长度，插入节点时，只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表中；内存分配不是在创建链表时一次性完成的，而是每添加一个节点分配一次内存。

典型的单向链表节点定义：

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

往链表末尾添加一个节点：

void add_to_tail(Node** phead, int value) {
    // 头结点是一个指针的指针
    Node* pnew = new Node();
    pnew->value = value;
    pnew->next = nullptr;
    if(*phead == nullptr) {
        // 创建头节点
        *phead = pnew;
    } else {
        // 添加节点到尾部
        Node* pnode = *phead;
        while(pnode->next != nullptr) {
            pnode = pnode->next;
        }
        pnode->next = pnew;
    }
}

想要在链表中找到第i个节点，那我们只能从头结点开始遍历链表，时间效率为O(n)，而在数组中只需要O(1)的时间。

找到第一个含有某值节点并删除该节点的代码：

void remove_node(Node** phead, int value) {
    if(phead==nullptr || *phead==nullptr) {
        return;
    }

    Node* p_delete = nullptr;
    if((*phead)->value == value) {
        // 头结点删除需要单独考虑操作
        p_delete = *phead;
        *phead = (*phead)->next;
    } else {
        Node* pnode = *phead;
        // 寻找删除节点的前一个节点
        while(pnode->next != nullptr
            && pnode->next->value != value) {
                pnode = pnode->next;
        }
        if(pnode->next != nullptr && pnode->next->value == value) {
            // 调整删除节点前一个节点的链接
            p_delete = pnode->next;
            pnode->next = pnode->next->next;
        }
    }

    if(p_delete != nullptr) {
        delete p_delete;
        p_delete = nullptr;
    }
}

一些特殊形式的链表也会被经常考到：

• 环形链表：链表末尾节点指向头结点（面试题62）；
• 双向链表：节点还有一个指向前一个节点的指针（面试题36）；
• 复杂链表：节点还有拥有指向任意节点的指针（面试题35）。

面试题6：从尾到头打印链表

输入一个链表的头节点，从尾到头反过来打印每个节点的值。

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

Tips：如果打算修改输入数据，最好先问面试官是不是允许修改，这里假设面试官不能改变链表的结构。

这道题目需要先访问的节点后输出，可以想到使用栈这种数据结构，每次访问到节点，就压到栈中，输出的时候只需要循环出栈即可。

完整代码实现：

#include <iostream>
#include <stack>

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

void add_to_tail(Node** phead, int value) {
    // 头结点是一个指针的指针
    Node* pnew = new Node();
    pnew->value = value;
    pnew->next = nullptr;
    if(*phead == nullptr) {
        // 创建头节点
        *phead = pnew;
    } else {
        // 添加节点到尾部
        Node* pnode = *phead;
        while(pnode->next != nullptr) {
            pnode = pnode->next;
        }
        pnode->next = pnew;
    }
}

void reverse_print(Node** phead) {
    if(phead==nullptr || *phead==nullptr) {
        return;
    }
    std::stack<Node*> pstack;
    Node* pnode = *phead;
    while(pnode != nullptr) {
        pstack.push(pnode);
        pnode = pnode->next;
    }
    while(!pstack.empty()) {
        pnode = pstack.top();
        printf("%d\t", pnode->value);
        pstack.pop();
    }
}

int main() {
    int values[] = {1, 2, 3, 4, 5};
    Node** phead = new Node*;
    *phead = nullptr;
    for(int i = 0; i < 5; i++) {
        add_to_tail(phead, values[i]);
    }
    reverse_print(phead);
    return 0;
}

具体的实现中需要注意到的一个点是头节点的初始化，因为是指针的指针，所以需要先申请一个Node指针类型的指针，new Node*，然后再将头结点指向的节点设置为nullptr，这样才不会在访问时出错。

如果可以使用栈结构来实现，也可以考虑使用递归的方式实现，通过递归访问，只有在返回函数的时候再输出节点，就可以实现逆序输出。

// 调用的时候要使用 *phead
void reverse_print_rec(Node* node) {
    if(node == nullptr) {
        return;
    }
    reverse_print_rec(node->next);
    printf("%d\t", node->value);
}

递归的代码相比于使用栈会简洁很多，但是使用递归是有代价的，函数递归使用的栈空间通常会有限制（比自己建立栈的空间要小），所以如果链表过于长可能会导致函数调用栈溢出。