今天刷题的时候再次遇到了链表，由于本人是自学，网上搜了很多关于链表的概念，有些感觉写的不错，有些云里雾里自己说错了都不知道，这里对链表这个结构做个详细的说明。
单链表
单链表中的每个结点包含值val，还包含链接到下一个结点的引用字段next。通过这种方式，单链表将所有结点按顺序组织起来。
Java中对一个链表的典型定义如下：
public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode(int x) { val = x; }
}在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
操作单链表
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。
- 往后添加节点
如果给了节点pre，怎么给它的下一个节点赋值x呢？
思路是新建一个节点cur，值为x，然后向后链接pre.next，再向前链接pre，这样自己就变成了pre的下一个节点了。
与数组不同的是，链表不需要将所有元素移动到插入元素之后。因此可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。
- 开头添加节点
我们使用头结点来代表整个列表。因此，在列表开头添加新节点时更新头结点 head 至关重要
思路：
- 初始化一个新结点
cur； - 将新结点链接到我们的原始头结点
head。 - 将
cur指定为head。
例如，让我们在列表的开头添加一个新结点 9 。
1、我们初始化一个新结点 9 并将其链接到当前头结点 23 。
2、指定结点 9 为新的头结点。
- 删除中间节点
思路：找到cur的上一个节点pre和自身的下一个节点cur.next，然后将pre.next = cur.next即可。跳过cur
需要从头结点遍历链表，时间复杂度为O(n)，n是链表长度。空间为O（1），只需要常量空间来存指针。
- 删除第一个节点
直接head = head.next即可。
- 删除最后节点
遍历找到倒数第二个节点（cur.next.next=null），将倒数第二个节点指向null，再将最后一个节点指向原来的倒数第二个节点
