---

🎈 作者F1a;Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏：C/C++面试通关集锦 （优质好文持续更新中……）🚀

---

目录

一、单链表

1.1 插入节点

1.2 删除结点

 二、双链表

2.1 插入节点

 2.2 删除节点

 三、单向循环链表

3.1 插入节点

3.2 删除结点

 四、双向循环链表

4.1 插入节点

 4.2 删除节点

 五、静态链表

六、实战讲解

6.1 链表插入排序

6.1.1 题目描述

6.1.2 算法思路

6.1.3 代码实现

6.1.4 复杂度分析

6.1.5 题目链接

6.2 合并两个有序链表

6.2.1 题目描述

6.2.2 算法思路

6.2.3 代码实现

6.2.4 复杂度分析

6.2.5 题目链接

6.3 反转链表

6.3.1 题目描述

6.3.2 算法思路

6.3.3 代码实现

6.3.4 复杂度分析

6.3.5 题目链接

6.4 单链表去重

6.4.1 题目描述

6.4.2 算法思路

6.4.3 代码实现

6.4.4 复杂度分析

6.4.5 题目链接

6.5 判断链表是否有环

6.5.1 题目描述

6.5.2 算法思路

6.5.3 代码实现

6.5.4 复杂度分析

6.5.5 题目链接

6.6 删除链表中倒数第 N 个结点

6.6.1 题目描述

6.6.2 算法思路

6.6.3 代码实现

6.6.4 复杂度分析

6.6.5 题目链接

6.7 移除链表中的元素

6.7.1 题目描述

6.7.2 算法思路

6.7.3 代码实现

6.7.4 复杂度分析

6.7.5 题目链接

七、总结

---

在日常的学习以及求职面试中，链表是一块非常重要的内容，经常被提及，本篇文章总结了链表的各种类型，包括：单链表、双链表、单项循环链表、双向循环链表、静态链表，接着会有大量真题实战，想不会都难！赶紧来看下吧！

一、单链表

单链表是一种最简单的链表形式，每个节点仅有一个指向下一个节点的指针（next 指针），因此，可以将节点连接成一条链，如下所示：

通常数据结构为：

struct node {
    int data;  // 存储数据
    struct node *next; // 指针
};

链表通常有一个头节点，比如上图 Head 所指向的节点，头节点可以存储数据，也可以不存储数据，添加不存储数据的头节点通常是为了便于处理链表。

1.1 插入节点

单链表插入节点有三步：

（1）获取插入位置前一个节点的指针；

（2）待插入节点的 next 指针指向下一个节点；

（3）前一个节点的 next 指针指向待插入节点；

如下图所示：

 

再来看一下动图：

 上述动图是在节点 2 后面插入节点 9，按照链表三步走的方式来，先找到插入节点的位置，然后待插入节点指向下一个节点，前一个节点指向待插入节点。

1.2 删除结点

单链表删除节点有二步：

（1）获取删除节点前一个节点的指针；

（2）前一个节点的指针指向下一个的下一个节点；

如下图所示：

 再来看一下动图：

 二、双链表

双向链表是指每个链表节点都有两个指针，分别指向前后节点，当前节点既可以直接访问下一个节点，也可以直接访问前一个节点。

如下所示：

 通常数据结构为：

struct node {
    int data;   // 存储数据
    struct node *next; // 指向下一个节点
    struct node *PRe;  // 指向前一个节点
};

2.1 插入节点

双链表插入节点有二步：

（1）获取插入位置前一个节点的指针；

（2）待插入节点的 next 指针指向下一个节点，下一个节点的 pre 指针指向待插入节点，前一个节点的 next 指针指向待插入节点，待插入节点 pre 指针指向前一个节点；（实现方法不唯一）

如下图所示：

再来看一下动图：

 2.2 删除节点

双链表删除节点有二步：

（1）获取删除节点的指针；

（2）删除节点前一个节点的 next 指针指向删除节点的下一个节点，即：node-pre->next = node->next，删除节点下一个节点的 pre 指针指向删除节点的前一个节点，即：node->next->pre = node->pre；（实现方法不唯一）

如下图所示：

 再来看一下动图：

 三、单向循环链表

单向循环链表将链表中的节点相连接，形成了一个环。如下所示：

通常数据结构为：

struct node {
    int data;  // 数据
    struct node *next; // 指针
};

数据结构的表示和单链表一样。

3.1 插入节点

单向循环链表插入节点有三步：

（1）获取插入位置前一个节点的指针；

（2）待插入节点的 next 指针指向下一个节点；

（3）前一个节点的 next 指针指向待插入节点；

如下图所示：

再来看一下动图：

 插入节点的方式和单链表一样，但是，单向循环链表可以从尾指针找到头指针。

3.2 删除结点

单向循环链表删除节点有二步：

（1）获取删除节点前一个节点的指针；

（2）前一个节点的 next 指针指向下一个的下一个节点；

如下图所示：

 再来看一下动图：

 四、双向循环链表

双向循环链表是指链表既有指向下一个节点的 next 指针，又有指向前一个节点的 pre 指针，而且还形成一个双向环，如下所示：

通常数据结构为：

struct node {
    int data;   // 存储数据
    struct node *next; // 指向下一个节点
    struct node *pre;  // 指向前一个节点
};

数据结构的表示和双链表一样。

4.1 插入节点

双向循环链表插入节点有二步：

（1）获取插入位置前一个节点的指针；

（2）待插入节点的 next 指针指向下一个节点，下一个节点的 pre 指针指向待插入节点，前一个节点的 next 指针指向待插入节点，待插入节点 pre 指针指向前一个节点；（实现方法不唯一）

如下图所示：

 再来看一下动图：

 4.2 删除节点

双向循环链表删除节点有二步：

（1）获取删除节点的指针；

（2）删除节点前一个节点的 next 指针指向删除节点的下一个节点，即：node-pre->next = node->next，删除节点下一个节点的 pre 指针指向删除节点的前一个节点，即：node->next->pre = node->pre；（实现方法不唯一）

如下图所示：

再来看一下动图：

 五、静态链表

静态链表是结合了顺序表和链表，通过数组实现了链表。

如下所示：

 通常数据结构表示为：

tyPEdef struct {
    int data;   // 存储数据
    int next;   // 数组下标
}SLink;

SLink g[NUM]; // 数组

六、实战讲解

6.1 链表插入排序

6.1.1 题目描述

给定链表的头指针，对给定的链表进行插入排序，使得链表升序排列。

6.1.2 算法思路

使用一个临时的头节点 tmpHead，因为如果要进行插入，每次都得从头开始进行插入。首先，判断当前节点是否大于等于前一个节点，如果是，则不需要插入，只需要移动节点即可，否则，从 tmpHead 处开始遍历链表，找到一个合适的位置插入当前节点。一直循环处理，直到处理完所有节点。

6.1.3 代码实现

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head) return head;  // 空链表直接返回
        ListNode* tmpHead = new ListNode(0);
        tmpHead->next = head;
        ListNode* pre = head, *curt, *tmp; // curt 为待排序的节点
        while (pre->next) { // pre->next 为待排序的节点
            curt = pre->next;
            if (pre->val <= curt->val) { // 如果大于或等于前一个节点，则直接移动到下一个节点
                pre = pre->next;
                continue;
            }
            tmp = tmpHead; // 从链表头开始遍历
            while (tmp->next->val <= curt->val) { // 寻找大于 curt 的节点
                tmp = tmp->next;
            }
            pre->next = curt->next;  // 先删除 curt 节点
            curt->next = tmp->next;  
            tmp->next = curt;
        }
        return tmpHead->next; // tmp 仅是临时使用的
    }
};

6.1.4 复杂度分析

@R_727_1304@：O(n^2)，几乎每次都需要从头遍历进行插入元素，链表长度为 n，每次遍历的复杂度为O(n)，故总的时间复杂度为O(n^2)；

空间复杂度：O(1)，这里仅仅使用到几个临时变量，可以忽略，故空间复杂度为O(1)；

6.1.5 题目链接

力扣

6.2 合并两个有序链表

6.2.1 题目描述

将两个升序链表合并为一个升序链表，新链表是通过拼接给定的两个链表的所有节点组成的。

6.2.2 算法思路

两个升序链表都是有序的，同时遍历两个升序链表，每次选取两个链表中值小的节点作为新链表的元素，直到所有元素都加入到新链表中，和归并排序中的合并算法一样。如下图所示：

6.2.3 代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;  // 一个链表为空，直接返回另一个
        if(!l2) return l1;

        ListNode* Head = new ListNode(0);
        ListNode* p = Head;
        while (l1 && l2) {
            if (l1->val <= l2->val) { // 比较两个链表元素
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }

        p->next = l1 ? l1 : l2;    // 将没有合并完了链表链接在结尾

        return Head->next;  // 头结点没用到，返回其下一个结点开始的链表
    }
};

6.2.4 复杂度分析

6.2.5 题目链接

力扣

6.3 反转链表

6.3.1 题目描述

已知单链表的头节点 head ，请反转该链表，并返回反转后的链表。

6.3.2 算法思路

我们拿链表中的任意三个连续的节点来举例（当然，一个或两个节点也成立），例如：A，B，C，要反转链表，只需执行如下四步即可：

（假设当前节点为 B）

（1）首先，暂存 B 的下一个节点 C；

（2）让 B->next 指向 A；

（3）当前节点指向 C；

一直重复上面三步，直到所有节点都遍历完。

6.3.3 代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pNode = head;
        ListNode *tmp = NULL, *pre = NULL; // tmp 用于暂存结点，pre 存储上一个结点
        while(pNode){
            tmp = pNode->next;  //暂存下一个结点的指针
            pNode->next = pre;   //当前节点指向前一个节点
            pre = pNode;         //更新前一个结点
            pNode = tmp;        //更新当前节点
        }
        return pre; //返回头节点
    }
};

6.3.4 复杂度分析

时间复杂度：O(n)，链表长度为 n，程序遍历一次链表，故时间复杂度为 O(n)；

空间复杂度：O(1)，因为没有用到额外的空间（next 变量可以忽略），故空间复杂度为O(1)；

6.3.5 题目链接

力扣

6.4 单链表去重

6.4.1 题目描述

给定一个按升序排列的链表，链表的头节点为 head ，要求删除所有重复的元素，使每个元素只出现一次 。

6.4.2 算法思路

题目中给出的是升序链表，故相同的元素连续在一起，比如：1->2->2->2->5->8->8->10，那么，去重的时候，只需要用当前节点与下一个节点的值进行比较，如果节点值相等，则让当前节点的next 指向下一个节点的 next，一直循环操作，直到遍历完所有节点。

6.4.3 代码实现

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* curt = head;
        while (curt->next) {
            if (curt->val == curt->next->val) { // 与下一个节点比较元素值
                curt->next = curt->next->next; // 相等则删除重复的节点
            } else {
                curt = curt->next; // 否则向后移动一个元素
            }
        }

        return head; // 返回链表头节点，头节点没有变
    }
};

6.4.4 复杂度分析

时间复杂度：O(n)，链表长度为 n，程序中遍历了一次链表，故时间复杂度为O(n)；

空间复杂度：O(1), 程序运行过程中，没有用到额外的空间，故时间复杂度为O(n)；

注意：有人可能会说，程序中使用到一个临时变量 curt，这种一个或两个的空间是相对于 n 是可以忽略的。

6.4.5 题目链接

力扣

6.5 判断链表是否有环

6.5.1 题目描述

给定一个链表，已知头节点 head，判断链表中是否有环。

6.5.2 算法思路

快慢指针法：

使用两个指针，慢指针每次移动一步，快指针每次移动两步，如果存在环，则快指针一定会追上慢指针。

6.5.3 代码实现

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 排除空链表和单个节点的情况
        if(head == NULL || head->next == NULL) return false;        
        ListNode *slow = head, *fast = head->next;
        while(slow != fast) {
            if(!fast || !fast->next) { // 判断是否为空
                return false;
            }           
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;                
    }
};

6.5.4 复杂度分析

时间复杂度：O(n)；

空间复杂度：O(1)；

6.5.5 题目链接

力扣

6.6 删除链表中倒数第 N 个结点

6.6.1 题目描述

给你一个链表，删除所给链表的倒数第 n 个结点，并且返回链表的头结点。

6.6.2 算法思路

双指针法：使用两个指针，First 和 second，让 first 先移动 n 步，second 指向头节点，然后，first 和 second 两个指针同时向后移动，当 first->next 为空的时候，second 指向的节点便是倒数第 n 个节点的前一个节点，这时候就可以删除倒数第 n 个节点了。

6.6.3 代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) { // 双指针法
        int i = 0;
        ListNode* first = head; // 首先，first 指针先移动 n 步
        while(i < n &amp;& first) {
            first = first->next;
            i++;
        }
        if(!first) return head->next; // 如果头指针是倒数第 n 个，官方数据里没有 n 大于链表长度的数据
        ListNode* second = head;
        while(first->next) { // 同时移动 first 和 second 指针
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next; // 删除倒数第 n 个指针
        return head;
    }
};

6.6.4 复杂度分析

时间复杂度：O(n)，只需要遍历一次链表，故时间复杂度为 O(n)；

空间复杂度：O(1)，仅用到两个指针以及一个变量，是常数级别的，可以忽略，故空间复杂度为O(1)；

6.6.5 题目链接

力扣

6.7 移除链表中的元素

6.7.1 题目描述

给定一个链表的头节点 head 和一个整数 val ，需要删除链表中所有满足 node->val == val 的节点。

6.7.2 算法思路

设置一个辅助头节点，依次遍历元素，如果等于 val 则删除节点，否则移动到下一个节点。

6.7.3 代码实现

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        ListNode* tmpHead = new ListNode(0); // 辅助头节点
        tmpHead->next = head;
        ListNode* curt = tmpHead; // 当前节点
        while (curt->next) {
            if (curt->next->val == val) { // 相等的话删除
                curt->next = curt->next->next;
            } else {
                curt = curt->next;
            }
        }
        return tmpHead->next;
    }
};

6.7.4 复杂度分析

6.7.5 题目链接

力扣

七、总结

链表适合于用在经常作插入和删除操作的地方，使用的时候注意要判断链表是否为空。

⭐好文推荐⭐

保姆级！超详解！远程连接Linux虚拟机！

一看就懂！保姆级实例详解 STL list 容器【万字整理】

最受欢迎的 Linux 竟然是它，Ubuntu 排第六 ？

   欢迎关注下方👇👇👇公众号👇👇👇，获取更多优质内容🤞（比心）！