数据结构动图详解链表（单链表双链表）

　　在日常的学习以及求职面试中，链表是一块非常重要的内容，经常被提及，本篇文章总结了链表的各种类型，包括：单链表、双链表、单项循环链表、双向循环链表、静态链表，接着会有大量真题实战，想不会都难！赶紧来看下吧！一、单链表
　　单链表是一种最简单的链表形式，每个节点仅有一个指向下一个节点的指针（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 复杂度分析
　　时间复杂度： O(n^2)，几乎每次都需要从头遍历进行插入元素，链表长度为 n，每次遍历的复杂度为O(n)，故总的时间复杂度为O(n^2)；
　　空间复杂度： O(1)，这里仅仅使用到几个临时变量，可以忽略，故空间复杂度为O(1)； 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.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.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.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.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 && 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.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 复杂度分析七、总结
　　链表适合于用在经常作插入和删除操作的地方，使用的时候注意要判断链表是否为空。