1. 单链表概念
对于所有的数据结构的基础都是创建+增删改查，学习链表重点也是学习链表的五种基本操作。
单向链表就像一个铁链一样，元素之间相互连接，包含多个结点，每个结点有一个指向后继元素的next指针。表中最后一个元素的next指向null。如下图：
对于单链表而言，一个结点只能有一个后继结点，但是可以多个结点指向同一个后继结点，如下图中c1被a2和b3同时指向。
在下图中c1结点有多个后继结点，则不满足链表的定义。
2. 创建链表
public class ListNode {
private int data;
private ListNode next;
public ListNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
}如果按照Java面向对象的理论，一个类中的属性权限修饰符应该为private，这体现了封装特性，别的方法想操作类ListNode中的值，只能通过类ListNode提供的get、set方法来实现。
/**
* 单链表的定义
* @author jay
*/
public class ListNode {
public int value;
public ListNode next;
public ListNode(int value) {
this.value = value;
next = null;
}
}通常的链表定义如上所示，属性权限修饰符为public，创建对象后能直接使用ListNode.value 和ListNode.next来操作，虽然违背了面向对象的设计要求，但是使得该代码更为精简，在算法题中广泛应用。
3. 链表的增删改查
3.1. 遍历链表
/**
* 获取链表长度
* @param head 链表头节点
* @return 链表长度
*/
public static int getLength(ListNode head) {
int length = 0;
ListNode listNode = head;
while (listNode != null) {
length++;
listNode = listNode.next;
}
return length;
}
3.2. 链表插入
3.2.1. 表头插入
（1）创建新结点newNode
（2）将新结点newNode连接到原来链表中的头结点，newNode.next = head
（3）将头指针指向新结点newNode，head = newNode
3.2.2. 中间插入
如果我们想在值为7的结点前插入新的结点，步骤如下
（1）创建新结点newNode
（2）找到7的前一个结点停下，newNode.next = listNode(15).next（图中虚线）
（3）15结点的下个结点指向newNode，listNode(15).next = newNode
步骤（2）和（3）顺序不能颠倒，假如先执行（3），便无法在找到结点7的地址，无法将newNode的将后续结点连接起来，见下图。
3.2.3. 结尾插入
（1）创建新结点newNode
（2）newNode.next = null
（3）将新结点newNode连接到原来链表中的尾结点，listNode(40).next = newNode
3.2.4. 代码
/**
* 链表插入
* @param head 链表头节点
* @param nodeInsert 待插入节点
* @param position 待插入位置，取值从2开始
* @return 插入后得到的链表头节点
*/
public static ListNode insertNode(ListNode head, ListNode nodeInsert, int position) {
// 需要判空，否则后面可能会有空指针异常
if (head == null) {
return nodeInsert;
}
// 越界判断
int size = getLength(head);
if (position > size + 1 || position < 1) {
System.out.println("位置参数越界");
return head;
}
// 在链表开头插入
if (position == 1) {
nodeInsert.next = head;
// 将头指针指向新插入的这个结点 返回头指针
head = nodeInsert;
return head;
}
// 在链表中间插入和在链表结尾插入
ListNode pNode = head;
int count = 1;
// 假如想插入的位置为5，那么需要找到位置4的结点并停下
while (count < position - 1) {
pNode = pNode.next;
count++;
}
nodeInsert.next = pNode.next;
pNode.next = nodeInsert;
return head;
}3.3. 链表删除
3.3.1. 删除表头结点
只需要执行head = head.next 就行了，如上图，将head向前移动一次之后，原来的结点不可达，会被JVM回收掉。
3.3.2. 删除最后一个结点
如果删除最后一个元素40，停在最后一个元素的前一个结点，直接执行cur.next = null，此时结点40变得不可达，最终会被JVM回收掉。
3.3.3. 删除中间结点
停在要删除元素的前一个结点，直接cur.next = cur.next.next，即可。
3.3.4. 代码
/**
* 删除节点
* @param head 链表头节点
* @param position 删除节点位置，取值从1开始
* @return 删除后的链表头节点
*/
public static ListNode deleteNode(ListNode head, int position) {
if (head == null) {
return null;
}
int size = getLength(head);
if (position > size || position <1) {
System.out.println("输入的参数有误");
return head;
}
if (position == 1) {
//curNode就是链表的新head
return head.next;
} else {
ListNode cur = head;
int count = 1;
while (count < position - 1) {
cur = cur.next;
count++;
}
ListNode curNode = cur.next;
cur.next = curNode.next;
}
return head;
}
