分门别类刷算法，坚持，进步！

刷题路线参考：https://github.com/youngyangyang04/leetcode-master

      https://github.com/chefyuan/algorithm-base

LeetCode通关：链表

在开始刷题之前，我们最好先了解一下链表的一些基础知识，那么现在，我们开始吧。

链表是一种链式存储的线性表，不要求逻辑上相邻的数据元素在物理位置上也相邻。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的引用。也可以称之为数据域和指针域。

入口节点称为头结点，最后一个节点指向null。

如图所示：

单链表

双链表，顾名思义，是有两个方向的链表。

每个节点除了有指向下一个节点的引用，还有指向上一个节点的引用。

双链表除了可以从前往后遍历，还可以从后往前遍历。

双向链表

循环链表，就是最后一个节点的后继指向头结点，头节点的前驱指向最后一个节点。

循环链表

我们知道链表在内存中不是连续分配的。链表是通过指针域的指针链接内存中的各个节点。

所以链表在内存中是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表内存分配

链表的定义主要包含两个部分：数据域和指针域。

在Java中因为屏蔽了指针的存在，我们的定义可以是数据，后继/前驱节点。

  • 单链表：
  1.  public class ListNode {
  2.       int val;
  3.       ListNode next;
  4.       ListNode(int x) { val = x; }
  5.   }
  • 双链表：
  1.  public class ListNode {
  2.       int val;
  3.       ListNode prev;
  4.       ListNode next;
  5.       ListNode(int x) { val = x; }
  6.   }

我们以单链表为例，来看一下链表的一些基本操作：

  • 删除节点

链表删除节点

  • 插入节点

插入节点

图中的插入和删除的时间复杂度都为O(1)。但是需要注意，这里的情况是插入和删除已经知道前趋节点的情况。

如果，还需要检索相应的节点，那么时间复杂度是O(n)。

☕ 题目：203. 移除链表元素 (https://leetcode-cn.com/problems/remove-linked-list-elements/)

❓ 难度：简单

版权声明：本文为three-fighter原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/three-fighter/p/15059673.html