单链表

单链表的每个结点，包含值和链接到下一个结点的引用字段。

//definition for singly-linked list.
struct SinglyListNode{
    int val;
    SinglyListNode *next;
    SinglyListNode(int x):val(x),next(Null){} //用头结点来表示整个列表
};

与数组不同，我们无法在常量时间内访问单链表中的随机元素。想知道第i个元素，需要从头结点逐个遍历，按照索引来访问元素平均花费O(N)时间，N为链表长度。

如访问第三个结点，我们需要使用头结点（23）中的next字段到达第二个结点（6），再次通过next访问第三个结点（15）。

A. 添加

用给定值初始化新的结点，将新的结点next链接到下一结点，再将当前结点的next链接到新结点。注意前后顺序，先让新来的结点有所指向（先给新来的画饼bushi

在链表开头添加新结点时，需要注意更新头结点(head)。

在链表末尾添加新结点时，初始化新结点cur，将cur的next-> NULL，遍历到链表尾部，直到结点的next为NULL，将该结点链接到cur。

B.删除

删除现有结点cur，先找到cur的上一结点prev和下一结点next，再将链接prev到next。

删除头结点时，可以直接将下一个结点分配为head。

删除最后一个结点时，找到next为NULL的结点cur，再将cur->NULL，删除最后的结点。

TMI：

评论区的其他方法：不需要找前序结点。

1.将当前结点的next结点赋值给当前结点，val=val->next；

2.此时有两个重复的结点，index->next=index->next->next;相当于删除了原来的next结点。

即将next结点的值保留给cur结点，再将next结点删除。

讨论：有人回复这条说这一方法没有区分结点的引用和结点对象本身。val=val->next；只是给了val一个新的引用ID，而并不能改变链表上指向val本身的链式结构，pre_node.next和node是两个不同的变量，因此改变node之后pre_node.next的值不变，链表结构也没有发生变化。

但是我感觉这样是可行的诶，如果val=val->next；只是为了赋值的话，虽然没有删除原结点，但是通过index->next=index->next->next;删去了后继结点，在值的体现上还是实现了同样的效果。不过原评论说第一步相当于把后继结点提前这一点，确实好像表达的不太对。