【理论】链表

链表类型

单链表

单链表中的指针域只能指向节点的下一个节点。

双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环链表

链表首尾相连，可以用来解决约瑟夫环问题。

链表的存储方式

链表在内存中不是连续分布的。

链表通过指针域的指针链接在内存中各个节点。

链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

链表的节点定义：

// 单链表
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {} //节点的构造函数
};

如果不定义构造函数，初始化时会使用默认构造函数初始化节点

ListNode* head = new ListNode(5); // 定义了构造函数

ListNode* head = new ListNode();
head->val = 5;

链表的操作

删除节点

在C++里最好手动释放这个D节点，释放这块内存。

其他语言例如Java、Python有内存回收机制，就不用手动释放。

添加节点

性能分析

链表经典题目

虚拟头结点

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
ListNode* cur = dummyHead;

基本操作

链表的增删改查

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点的数值

class MyLinkedList {
public:
    struct Node{
        int val;
        Node* next;
        Node(int val):val(val), next(nullptr){}
    };

    MyLinkedList() {
        _dhead=new Node(0);
        _size=0;
    }
    
    int get(int index) {
        if(index>(_size-1)||index<0){
            return -1;
        }
        Node* cur=_dhead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        Node* newnode=new Node(val);
        newnode->next=_dhead->next;
        _dhead->next=newnode;
        _size++;
        // printLinkedList();
    }
    
    void addAtTail(int val) {
        Node* newnode=new Node(val);
        Node* cur=_dhead;// 这里不->next的原因是：addAtTail的题意中链表可能为空
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        cur->next=newnode;
        _size++;
        // printLinkedList();
    }
    
    void addAtIndex(int index, int val) {
        if(index>_size)return;
        if(index<0)index=0;
        Node* newnode=new Node(val);
        Node* cur=_dhead;
        while(index--){
            cur=cur->next;
        }
        newnode->next=cur->next;
        cur->next=newnode;
        _size++;
        // printLinkedList();
    }
    
    void deleteAtIndex(int index) {
        if(index>=_size||index<0)return;
        Node* cur=_dhead;
        while(index--){
            cur=cur->next;
        }
        Node* tmp=cur->next;
        cur->next=cur->next->next;
        delete tmp;
        tmp=nullptr;
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        _size--;
        // printLinkedList();
    }

    // 打印链表
    void printLinkedList() {
        Node* cur = _dhead;
        while(cur->next!=nullptr){
            cout<<cur->next->val<<" ";
            cur=cur->next;
        }
        cout<<endl;
        cout<<"size:"<<_size<<endl;
    }

private:
    int _size;
    Node* _dhead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

 反转链表

动画应该是先移动pre，再移动cur

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur=head;
        ListNode *prev=NULL;
        while(cur!=nullptr){
            ListNode *next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};

 删除倒数第N个节点、链表相交、环形链表

使用双链表

总结