单链表的结点定义

struct ListNode {
    int val;
    ListNode *next;
    // ListNode() : val(0), next(nullptr) {}
    // ListNode(int x) : val(x), next(nullptr) {}
    // ListNode(int x, ListNode *next) : val(x), next(next) {}
};

单链表的实现

头结点存在 + 堆版本

struct ListNode {
    int val;
    ListNode *next;
};

class List {
private:
    ListNode *head;
public:
    List(){
        this->head = new ListNode;
        this->head->next = NULL;
    }
    ~List(){
        ListNode *pre = head;
        ListNode *cur = head->next;
        while(cur){
            // 删除
            pre->next = NULL;
            delete pre;
            // 保证循环
            pre = cur;
            cur = cur->next;
        }
    }

    // 头插法
    void insert_head(int val){
        ListNode *node = new ListNode;
        node->val = val;
        // 先连起来插入结点后面的结点， 再连插入结点前面的head结点
        node->next = head->next;
        head->next = node;
    }

    // 查找值，删除
    void delete_val(int val){
        ListNode *pre = head;
        ListNode *cur = head->next;
        while(cur){
            if(cur->val == val){
                // 先将前面结点连到后面的结点，再删除本结点
                pre->next = cur->next;
                // 删除
                cur->next = NULL;
                delete cur;
                return;
            }
            // 保证循环
            pre = cur;
            cur = cur->next;
        }
    }
}

链表遍历

链表

// 推荐

ListNode* cur = head;
while(cur){
    cout << cur->val << endl;
    cur = cur->next;
}
// cur = nullptr，最后一个结点的下一个，是空。

但不要为了让cur最后指向最后的结点，而让while变得特别麻烦，这样很容易忘了第一个条件而出错，即while(cur->next)，若传入空链的情况下，空结点怎么可能有next。

// 不推荐

// while(cur->next) 就错了
while(cur != NULL && cur->next != NULL){
    cout << cur->val << endl;
    cur = cur->next;
}
cout << cur->val << endl;
// cur = 最后一个结点，非空。