一、链表理论基础

1. 什么是链表

什么是链表？链表是一种通过指针串联在一起的线性结构，每一个结点由两部分组成，一个是数据域（存放数据），另一个是指针域（存放指向下一个节点的指针），最后一个结点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头节点，也就是 head。
如图所示：

2. 链表的类型

（1) 单链表

单链表

上面说的就是单链表

（2）双链表

双链表

单链表中的节点只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表既可以向后查询，也可以向前查询。

如图所示：

（3）循环链表

循环链表，顾名思义，就是将链表的首尾相连。
循环链表可以用来解决 约瑟夫环 问题。

3. 链表的存储方式

数组在内存中的分布是连续的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中的各个节点，组成的一串不连续的存储空间。
所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某个地址上，分配机制取决于操作系统的内存管理。

如图所示：

这个链表的起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起。

4. 链表的定义

链表节点的定义，看似简单，但实际上很多人面试的时候都写不好。
这是因为平时在刷 LeetCode 的时候，链表的节点都默认定义好了，直接用就行了，所以大家都没有注意到链表的节点是如何定义的。
而在面试的时候，我们是需要自己手写链表的。

以下是 C/C++定义链表节点的方式：

// 单链表
class ListNode{
    int val;        // 数据域
    ListNode *next;    // 指针域
    ListNode(int x) : val(x), next(null) {}        // 节点的构造函数
}

链表的定义可以不写构造函数吗？答案是可以的，C++会帮我们生成一个默认构造函数。
但是这个构造函数不会初始化任何成员变量。
举个例子：

// 自己写了构造函数
ListNode *head = new ListNode(5);

// 使用默认构造函数
ListNode * head = new ListNode();
head->val = 5;

如果不定义构造函数，使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

5. 链表的操作

（1）删除节点

删除节点D，如下：

只要将 C 节点的 next 指针指向 E 节点就可以了。
那有人会说了，D节点不是依然存留在内存里吗？只不过是没有在这个链表里而已。
确实是这样，所以在C++里最好是再手动释放这个D节点，释放这块内存。
其他的语言，例如Java、Python，就有自己的内存回收机制，不再需要程序员手动释放了。

（2）添加节点

如图所示：

可以看出链表的增添和删除都是 O(1) 操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点，然后通过next指针进行删除操作，查找的时间复杂度是 O(n)。

6. 性能分析

链表的特性和数组的特性的比较，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

二、移除链表元素

1. 移除链表元素

（1）能够访问头节点

203. 移除链表元素 - 力扣（LeetCode）

我觉得代码随想录已经说的很好了，而且这道题也简单，看代码随想录的题解就可以了。移除链表元素

这是我的代码:

/**
 * 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* removeElements(ListNode* head, int val) {
        // 如果删除的是头节点
        while(head != nullptr && head->val == val){
            ListNode* temp = head;
            head = head->next;
            delete temp;        // 释放内存
        }
        // 如果删除的不是头节点
        ListNode* curptr = head;
        while(curptr != nullptr && curptr->next != nullptr){
            if(curptr->next->val == val){
                ListNode* temp = curptr->next;
                curptr->next = curptr->next->next;
                delete temp;
            }
            else{
                curptr = curptr->next;
            }
        }
        return head;
    }
};

（2）无法访问头节点

237. 删除链表中的节点 - 力扣（LeetCode）

方法：和下一个节点交换

删除链表中的节点的常见的方法是定位到待删除结点的上一个结点，修改上一个结点的 next 指针，使其指向待删除节点的下一个节点，即可完成删除操作。

这道题中，传入的参数 node 为要被删除的节点，无法定位到该节点的上一个节点。注意到要被删除的节点不是链表的末尾节点，因此 node.next 不为空，可以通过对 node 和 node.next 进行操作实现删除节点。

在给定节点 node 的情况下，可以通过修改 node 的 next 指针的指向，删除 node 的下一个节点。但是题目要求删除 node，为了达到删除 node 的效果，只要在删除节点之前，将 node 的节点值修改为 node.next 的节点值即可。
例如：给定链表 4 —> 5 —> 1 —> 9，要被删除的节点值是 5，即链表中的第2个接待你。可以通过如下两步操作实现删除节点的操作。

将第2个节点的值修改为第3个节点的值，即将节点5的值修改为1，此时链表如下：

4 —> 5 —> 1 —> 9

删除第3个节点，此时链表如下：

4 —> 1 —> 9
至此，题解。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        // 因为题目给的是要删除当前的节点，所以获取不到当前节点的前一个结点
        // 但是题目又说，被删除的结点不是尾节点，所以我们想到当前将下一个节点的赋给当前要删除的节点，然后删掉下一个节点，这样就等价于删除了当前节点
        // 因为这样，即使题目要删除的是头节点，我们通过交换，删除的是下一个节点，所以不用分情况讨论
        ListNode* temp = node->next;
        node->val = node->next->val;
        node->next = node->next->next;
        delete temp;        // 释放内存
    }
};

2. 设计链表

（1）设计一个完整的链表

707. 设计链表 - 力扣（LeetCode）

写这道题主要是对链表还不是很熟悉，而且卡在一个地方，就是在编译器写的时候是可以使用内部类的，但是在力扣平台上不知道为什么用不了，所以写了结构体，当然这个结构体也可以提到类的外部。其他的都没什么大问题，多写就行了。

class MyLinkedList {
public:
    // 链表节点
    struct LinkedNode{          // 定义链表节点的结构
        int val;
        LinkedNode* next;
        LinkedNode(int val) : val(val), next(nullptr){}
    };
    MyLinkedList() {        // 构造函数
        _dummyHead = new LinkedNode(0);
        _size = 0;          // 虚拟头节点不算入真正链表的结点
    }
    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if(index < 0 || index > _size - 1){     // 索引无效
            return -1;
        }
        LinkedNode* curptr = _dummyHead;         // 虚拟头指针赋给当前需要操作的指针
        while(index--){
            curptr = curptr->next;
        }
        return curptr->next->val;
    }
    void addAtHead(int val) {
        LinkedNode* newHead = new LinkedNode(val);  // 新的头节点
        newHead->next = _dummyHead->next;
        _dummyHead->next = newHead;
        _size++;
    }
    void addAtTail(int val) {
        LinkedNode* newTail = new LinkedNode(val);  // 新的尾节点
        LinkedNode* curptr = _dummyHead;
        while(curptr->next != nullptr){             // 定位到尾节点
            curptr = curptr->next;
        }
        curptr->next = newTail;
        _size++;
    }
    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    void addAtIndex(int index, int val) {
        if(index > _size){
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* curptr = _dummyHead;
        while(index--){   // 找到要插入位置的前一个节点
            curptr = curptr->next;
        }
        newNode->next = curptr->next;
        curptr->next = newNode;
        _size++;
    }
    void deleteAtIndex(int index) {
        if(index < 0 || index > _size - 1){
            return;
        }
        LinkedNode* curptr = _dummyHead;
        while(index--){
            curptr = curptr->next;
        }
        LinkedNode* temp = curptr->next;
        curptr->next = curptr->next->next;
        delete temp;
        _size--;
    }
    // 打印链表
    void display(){
        LinkedNode* cur = _dummyHead->next;
        while(cur != nullptr){
            cur = cur->next;
            cout << cur->val << " ";
        }
        cout << endl;
    }
private:
    LinkedNode* _dummyHead;  // 虚拟头节点
    int _size;               // 链表的节点数，即链表的大小
};
/**
 * 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);
 */

扩展：可以试试用双链表来解，双链表需要开一个虚拟头节点和一个虚拟尾节点，同时需要一个 _size 来记录链表的大小，我们通过 _size - index 更接近虚拟头还是虚拟尾，来确定从那边开始操作，这样会让程序的效率提高。

3. 反转链表

（1）反转整个链表

① 迭代的思想

206. 反转链表 - 力扣（LeetCode）
思路：
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的 next 指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示：

之前链表的头节点是元素1，反转之后头节点就是元素5，这里并没有添加或者删除节点，仅仅是改变next指针的方向。
接下来看一看是如何反转的？

双指针法：

/**
 * 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* temp;                    // 保存下一个节点的指针
        ListNode* pre = nullptr;        // pre指向空指针
        ListNode* cur = head;            // cur指向头指针
        while(cur != nullptr){            // cur需要遍历一遍指针
            temp = cur->next;            // 先将下一个节点保存再temp
            cur->next = pre;            // 实现第i个节点的反转
            // 更新pre和cur指针，因为最后我们要通过pre来访问反转后的链表
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

② 递归思想

力扣有位大牛 labuladong 对递归反转链表总结的很好https://mp.weixin.qq.com/s/5wz_YJ3lTkDH3nWfVDi5SA

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。
处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。
值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是O(n)，但是迭代解法的空间复杂度是O(1)，而递归解法需要堆栈，空间复杂度是O(n)。但是用递归写的代码看起来更加简洁、优美。考虑效率的话还是使用迭代算法更高。

/**
 * 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) {
        if(head == nullptr){
            return head;
        }
        if(head->next == nullptr){      // 递归出口,如果要反转的节点只剩下一个，则直接返回本节点
            return head;
        }
        ListNode* last = reverseList(head->next);
        head->next->next = head;        // 让下一个节点指向它的上一个节点
        head->next = nullptr;           // 上一个节点指向空
        return last;                    // 递归完成后last指针指向原来链表的最后一个节点，也就是反转后的第一个节点
    }
};

（2）回文链表

垃圾算法，时间复杂度 O(3n)，空间复杂度 O(n)

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode* temp;
        ListNode* pre = nullptr;
        ListNode* cur = head;           // cur指针用来遍历链表
        // 开了一个新链表，垃圾算法来着
        ListNode* newHead = new ListNode();
        ListNode* ptr = newHead;
        while(cur != nullptr){
            ListNode* newNode = new ListNode();
            newNode->val = cur->val;
            ptr->next = newNode;
            ptr = ptr->next;
            cur = cur->next;
        }
        cur = head;
        ptr = newHead->next;
        while(cur != nullptr){
            temp = cur->next;           // 指向下一个节点
            cur->next = pre;
            // 更新pre和cur
            pre = cur;
            cur = temp;
        }
        while(pre != nullptr && ptr != nullptr){
            if(pre->val != ptr->val){
                return false;
            }
            pre = pre->next;
            ptr = ptr->next;
        }
        return true;
    }
};

时间复杂度 O(n)，空间复杂度 O(1)

思路：

代码：

/**
 * 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* reverse(ListNode* head){
        ListNode* temp = nullptr;
        ListNode* pre = nullptr;
        ListNode* cur = head;           // cur指针用来遍历链表
        while(cur != nullptr){
            temp = cur->next;           // temp保存cur下一个节点的指针域
            cur->next = pre;            // 让cur指向nullptr
            pre = cur;                  // 更新pre和cur
            cur = temp;
        }
        return pre;                     // pre才是反转后链表的头节点
    }
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr){ 
            return true;
        }
        ListNode* slow = head;          // 慢指针，每次移动一个位置，用来记录链表的中间位置
        ListNode* fast = head;          // 快指针，每次移动两个位置，走完链表，让slow能够走到链表的中间位置
        ListNode* pre = head;           // pre指向slow的前一个位置,用来分割链表
        while(fast != nullptr && fast->next != nullptr){    // 目的是让slow能够指向链表的中间位置
            pre = slow;                 // pre指向slow的前一个位置
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;            // 将链表前半部分断开
        ListNode* cur1 = head;          // 链表前半段
        ListNode* cur2 = reverse(slow); // 链表后半段
        while(cur1 != nullptr){         // 两个链表开始比较,cur1段链表的长度一定小于cur2,所以使用cur1作为循环的长度
            if(cur1->val != cur2->val){
                return false;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return true;
    }
};

4. 交换链表中的节点

（1）两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：
一定要画图。
情况一：

情况二：

先定义一个快指针和一个慢指针，指向交换节点前的链表的头（也就是节点1），因为题目不允许修改节点的值，所以只能改变节点指针域的指向以达到交换节点的效果。首先要考虑清楚链表的结点数量是偶数个还是奇数个？偶数个意味着每两个节点都需要交换，那么 slow->next = fast->next->next->next；如果是奇数个，那么 slow->next = fast->next->next；
注意：交换后最后一个节点的指针域一定要指向一个空指针，不然链表就死循环了。

代码：

/**
 * 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* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr){   // 如果是空链表或只有一个节点，那么直接返回
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        head = head->next;
        while(fast && fast->next){     // fast或fast->next为空，表明没有节点或只有一个节点,这时不再需要交换了
            fast = fast->next->next;
            slow->next->next = slow;
            if(fast == nullptr){        // 如果fast节点不存在，那么slow->next则需要指向一个空指针，不然链表陷入死循环
                slow->next = nullptr;
            }
            else{
                if(fast->next == nullptr){  // 如果 fast->next不存在，那么表明链表的个数是奇数，最后一个节点不需要交换(因为没有)
                    slow->next = fast;
                }
                else{                        // 链表节点是偶数个
                    slow->next = fast->next;
                }
            }
            slow = fast;
        }
        return head;
    }
};

5. 删除链表的倒数第N个节点

19. 删除链表的倒数第N个节点 - 力扣（LeetCode）

我的解法
时间复杂度O(n)
控件复杂度O(1)

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(-1);     // 虚拟头节点
        dummyHead->next = head;
        ListNode* cur = head;
        int size = 0;                       // 记录链表的大小
        while(cur != nullptr){
            cur = cur->next;
            size++;
        }
        int moveNumber = size - n;      // 链表正向移动的节点数
        cur = dummyHead;                // cur指针指向虚拟头节点
        while(moveNumber > 0){
            cur = cur->next;
            moveNumber--;
        }
        cur->next = cur->next->next;        // 删除指定的节点
        return dummyHead->next;
    }
};

递归思想：

/**
 * 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:
    int cur = 0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr){ return nullptr; }
        // 这里为什么要用 head->next 来接收递归的返回值呢？很巧妙的，当递归到最后一层时，递归开始往回走
        // 它会返回最后一个节点(形参head->next)，即相当于把 head->next 返回给 head->next，这样子head->next也会跟着往前走
        // 知道走到链表的第一个节点的位置。
        head->next = removeNthFromEnd(head->next, n);
        cur++;
        if(cur == n){ return head->next; }      // 如果当前的节点是要删除的节点，就返回它的下一个节点，即我们忽略要删除的节点
        return head;
    }
};

6. 链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

思路：
简单来说，就是求两个链表相交的指针，注意这里的相交指的并不是链表节点的值相同，而是指针相同。
我们可以求出两个链表的长度，然后求出他们的长度差 num，通过这个长度差，让更长的链表先移动 num个节点数，然后这个时候他们就在同一起跑线上了，我们可以同时让他们往后移动，判断这两个指针是否相等就行了，至此题解。

复杂度分析：
时间复杂度O(n + m)
空间复杂度O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A_head = headA;
        ListNode* B_head = headB;
        int A_size = 0;             // 记录链表A和链表B的长度
        int B_size = 0;
        while(A_head != nullptr){   // 记录A的大小
            A_head = A_head->next;
            A_size++;
        }
        while(B_head != nullptr){   // 记录B的大小
            B_head = B_head->next;
            B_size++;
        }
        A_head = headA;
        B_head = headB;
        if(A_size < B_size){        // 不管A和B谁更长，最终我们都让A_head指向更长的那条链表
            swap(A_size, B_size);
            swap(A_head, B_head);
        }
        int num = A_size - B_size;     // A、B链表节点的数量差
        while(num > 0){                 // 链表A先移动 num 个节点
            A_head = A_head->next;
            num--;
        }
        while(A_head != nullptr){
            if(A_head == B_head){ return A_head; }
            A_head = A_head->next;
            B_head = B_head->next;
        }
        return nullptr;
    }
};

7. 环形链表

（1）环形链表II

142. 环形链表 II - 力扣（LeetCode）

思路：
代码随想录，环形链表 II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head != NULL && head->next != NULL){
            ListNode* cur = head;
            ListNode* slow = head;      // 慢指针
            ListNode* fast = head;      // 快指针
            while(fast != NULL && fast->next != NULL){      // 若fast指针或它的下一个指针为空，表明链表有尽头，即没有环
                fast = fast->next->next;    // fast指针每次移动两个位置
                slow = slow->next;          // slow指针每次移动一个位置
                if(slow == fast){           // 如果相遇表示链表存在环
                    ListNode* index1 = fast;
                    ListNode* index2 = head;
                    while(index1 != index2){
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index2;
                }
                cur = cur->next;
            }
        }
        return NULL;
    }
};

（2）环形链表

141. 环形链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head != NULL && head->next != NULL){
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast && fast->next){            // 边界问题需要注意
                fast = fast->next->next;        // fast指针一次走两步
                slow = slow->next;              // slow指针一次走一步
                if(slow == fast){
                    return true;
                }
            }
        }
        return false;
    }
};