一，单链表结构定义
C/C++ 数组：一组具有相同类型数据的集合。结构体：不同类型数据的集合。
// Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 复制代码
二，写链表代码的技巧
2.1，技巧一：理解指针或引用的含义
指针：指针存放某个对象地址。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。
2.2，警惕指针丢失和内存泄露
- 插入节点时，一定要注意操作是顺序；
- 删除链表时，也一定要记住手动释放内存空间。
2.3，利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。head = null 表示链表中没有节点，head 表示头节点，指向链表中的第一个节点。
引入哨兵节点，哨兵节点不管链表是否空，head 指针都会已知指向哨兵节点。有哨兵节点的链表叫作带头链表，反之则是不带头链表。
利用哨兵简化编程难度的技巧再插入排序、归并排序、动态规划等代码中都有用到。
2.4，重点留意边界处理条件
写链表代码一定要检查以下情况下，代码逻辑能否正常工作。
- 链表为空；
- 链表只有一个节点；
- 代码处理头节点和尾节点
2.5，举例画图，辅助思考
处了举例画图辅助我们思考问题之外，剩下最关键的就是多写多练、熟能生巧。 5 个常见链表操作如下：
- 单链表反转
- 链表中环的检测
- 两个有序链表的合并
- 删除链表倒数第
n个节点 - 求链表的中间节点
