前情提要：在学习 ArrayList 时，认识到由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。
目录
一、链表概念与结构
链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序的通过链表中的引用链接次序实现的。
其结构总共有8种：
带头链表中的第一个节点相当于一个标记，如果采用头插法新增节点，只能在当前头的下一个节点插入；而如果是不带头的链表，头插法是在第一个节点前面新增节点。
二、当向单链表的实现
整个实现将围绕下图展开：
定义一个 cur 对象，表示当前节点。用法：遍历链表。
注意
1、cur 为空和 cur.next 为空的区别。 2、单向链表不能回退。
2.1 准备工作
1、先定义一个类用来表示整个链表，名为 SingleLinkedList。
2、而链表中包含节点，每个节点带有两个域，一个是数据域存储整型数据；另一个是指针域，指针域中存放的是下一个 节点 的引用，因此其类型也就是节点；且注意两个属性都用 public 修饰，在测试时大有用途。将每个节点封装成链表的内部类。
3、定义一个头部节点，用于查找或者输出链表数据，但这里并不代表链表带头。
4、将对链表的操作封装成一个接口，其功能包括打印链表数据 display、计算链表长度 size、查找数据 contains、头插法插入数据 addFirst、尾插法插入数据 addLast、任意位置插入数据 addIndex、删除第一次出现 key 的节点 remove、删除所有值为 key 的节点 removeAllKey、清空。
SingleLinkedList 链表：
package test;
// 不带头 单向 链表
public class SingleLinkedList implements ILink{
static class ListNode{ // 每一个 节点 都是对象，具有共同属性，因此可以抽象成内部类
public int val;
public ListNode next; // 节点的地址，类型也应该是节点的类型
public ListNode(int val){
this.val = val;
}
}
public ListNode head; // 头节点
@Override
// ......
}ILink 接口：
package test;
/**
* 链表的操作
*/
public interface ILink {
//头插法
void addFirst(int data);
//尾插法
void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
boolean contains(int key);
//删除第一次出现关键字为key的节点
void remove(int key);
//删除所有值为key的节点
void removeAllKey(int key);
//得到单链表的长度
int size();
// 清空
void clear();
// 打印链表数据
void display();
}在实现具体的操作之前，还需要考虑链表是否为空，即 head == null ?
2.2 初始化链表
在具体实现各项功能之前，需要有一个原始的链表，利于展示操作效果。其定义方法如下
package test;
public class SingleLinkedList implements ILink{
// ......
public void creatList(){ // 创建一个原始链表
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
this.head = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
}
// ......
}2.3 打印数据、链表长度、查找数据
这三个功能都需要将链表从头到尾遍历一遍。而遍历的条件只是当前节点不为空。
package test;
public class SingleLinkedList implements ILink{
// ......
@Override
public void display() {
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println(); // 换行
}
@Override
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
@Override
public boolean contains(int key) {
ListNode cur = head;
while (cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
}package test;
public class TestSingle {
public static void main(String[] args) {
// ILink iLink = new SingleLinkedList(); // 通过接口无法调用 creatList()
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.creatList(); // 还没实现新增节点功能前调用的原始链表
linkedList.display();
System.out.println(linkedList.size());
}
}2.4 头插法
@Override
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
newNode.next = head;
this.head = newNode;
}即使原先的链表是空的，代码一样能实现头插法插入节点。
2.5 尾插法
@Override
public void addLast(int data) {
ListNode newNode = new ListNode(data);
if (head == null){ // 原来链表中一个节点都没有的情况下
head = newNode;
return;
}
ListNode cur = head;
while (cur.next != null){
cur = cur.next;
} // 循环走完说明 cur.next == null 了
cur.next = newNode;
}package test_8_7;
public class TestSingle {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
// 实现新增节点功能之后，不需要调用 creatList()，也可以创建链表
// 头插法
linkedList.addFirst(11);
linkedList.addFirst(22);
linkedList.addFirst(33);
linkedList.addFirst(44);
// 尾插法
linkedList.addLast(55);
linkedList.display();
System.out.println(linkedList.size());
}
}2.6 任意位置插入节点
注意
1、指定位置的合法性；
2、指定下标为 0 和 指定位置等于链表长度 的情况分开处理；
3、单向链表不能回退，因此注意 cur 的位置；
4、所有的插入，优先绑定后面的节点。
@Override
public void addIndex(int index, int data) throws IllegalIndexException{
int len = this.size(); // 存储当前长度，好处：提高效率
if (index < 0 || index > len){
throw new IllegalIndexException("指定位置不合法！！！");
}else {
if (index == 0){
this.addFirst(data);
return;
}
if (index == len){
this.addLast(data);
return;
}
ListNode newNode = new ListNode(data);
ListNode cur = head;
while (index - 1 != 0){
cur = cur.next;
index--;
}
newNode.next = cur.next;
cur.next = newNode;
}
}package test;
// 处理指定位置的不合法异常
public class IllegalIndexException extends RuntimeException{
public IllegalIndexException(){
}
public IllegalIndexException(String msg){
super(msg);
}
}2.7 删除第一次出现 key 的节点
@Override
public void remove(int key) {
if (head == null){
return;
}
if(head.val == key){
head = null;
}
ListNode cur = findNodeOfKey(key);
if (cur == null){
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
public ListNode findNodeOfKey(int key){ // 找到存储的数据是key的对象，并返回
ListNode cur = head;
while (cur.next != null){
if (cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}提示
1、在链表中查找 key 可封装成一个方法
2、查找 key 的条件 cur.next 不为空的前提下，已经判断了 cur.next 存储的数据是否等于 key 了
2.8 删除链表中所有数据为 key 的节点
@Override
public void removeAllKey(int key) {
if (head == null){
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null){
if (cur.val == key){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
if (head.val == key){
head = head.next;
}
}2.9 清空
像之前“清空” ArrayList 的方法在链表中是不可行的，因为如果引用一直存在，那么引用所指的对象无法被内存回收，容易造成内存泄漏，因此只有将 next 都置空了才算清空了链表数据。
@Override
public void clear() {
ListNode cur = this.head;
while (cur != null){
ListNode prev = cur.next;
cur.next = null;
cur = prev;
}
head = null;
}三、面试题
3.1 删除链表中等于给定值 key 的所有节点。（与上面的 2.8 一个意思）
3.2 反转一个单链表。
public ListNode reverseList() { // 反转
if(head == null){
return null;
}
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode curNode = cur.next;
cur.next = head;
head = cur;
cur = curNode;
}
return head;
}3.3 返回链表中的中间节点，如果有两个中间节点，则返回第2个节点。
提示，不能通过计算链表长度的方法进行编程。
那么，采用双指针的方法，快指针走两步，慢指针走1步，最后慢指针指向的就是中间。
public ListNode middleNode() { // 找中间节点
ListNode fast = head; // 快指针，走两步
ListNode slow = head; // 慢指针，走一步
while(fast != null && fast.next != null){ // &&前面必须是 fast != null 的条件
fast = fast.next.next;
slow = slow.next;
}
/*while(fast.next != null && fast != null){ // 输出 NullPointerException
fast = fast.next.next;
slow = slow.next;
}*/
return slow;
}3.4 输出该链表中倒数第 k 个节点。
虽然 leetcode 上已经保证了 k 的合法性，但自己实现的时候还是需要注意 k 的有效范围。
public int kthToLast(int k) { // 返回倒数第k个字节的数据
if(head == null){
return -1;
}
// 注意k的范围
if (k <= 0){
return -1;
}
/*if (k > 5){ // 这样写还得求链表的长度，不好
return -1;
}*/
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count != k-1){ // 为了与慢指针拉开一定的距离
fast = fast.next;
if(fast == null) // 这里就是判断k是否超出链表长度的条件
return -1;
count++;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow.val;
}3.5 合并两个有序链表并按升序排序成有序链表返回。
提示
1、创建一个头节点，作为标志，可存储数据，但该数据无实际意义；
2、返回的节点不是创建的头节点。
3、在自己实现的链表中实现时，需要注意，因为该方法操作的是两个链表，因此不好将它定义到 SingleLinkedList 这个类中，因此直接定义到测试类。但直接定义到测试类时因为 ListNode 是 SingleLinkedList 的内部类，需要用 SingleLinkedList. 来调用 ListNode
package test;
public class TestSingle {
public static SingleLinkedList.ListNode mergeTwoLists
(SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) { // 合并两个有序链表并排序
SingleLinkedList.ListNode newHead = new SingleLinkedList.ListNode(-1); // 随便传一个数据，因为这个数据无效
SingleLinkedList.ListNode tmp = newHead;
while(headA != null && headB != null){
if (headA.val < headB.val){
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else{
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if (headA != null){
tmp.next = headA;
}
if (headB != null){
tmp.next = headB;
}
return newHead.next;
}
public static void main(String[] args) {
// 测试合并两个链表
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addFirst(4);
linkedList.addLast(11);
linkedList.addLast(19);
linkedList.addLast(44);
SingleLinkedList linkedList2 = new SingleLinkedList();
linkedList2.addFirst(3);
linkedList2.addLast(6);
linkedList2.addLast(32);
linkedList2.addLast(57);
SingleLinkedList.ListNode newNode = mergeTwoLists(linkedList.head, linkedList2.head);
linkedList.display(newNode);
}
}
3.6 以 x 值为基准将链表分割成两部分，所有小于 x 的节点排在大于或等于 x 的节点之后。
public ListNode partition(int x) { // 不改变原来数据的顺序下，将所有小于x的结点排在其余结点之前
ListNode beforeStart = null; // 小于x的头节点
ListNode beforeEnd = null; // 小于x的尾节点
ListNode afterStart = null; // 大于x的头节点
ListNode afterEnd = null; // 大于x的尾节点
ListNode cur = head;
while(cur != null){
if(cur.val < x){
if(beforeStart == null){ // 第一次插入
beforeStart = beforeEnd = cur;
}else{
beforeEnd.next = cur;
beforeEnd = beforeEnd.next;
}
}else{
if(afterStart == null){
afterStart = afterEnd = cur;
}else{
afterEnd.next = cur;
afterEnd = afterEnd.next;
}
}
cur = cur.next;
}
// 如果没有小于x的节点
if (beforeStart == null){
return afterStart;
}
// 前后两部分衔接起来
beforeEnd.next = afterStart;
// 第2部分的最后一个节点的引用要置空，否则编译超出范围
if(afterStart != null){
afterEnd.next = null;
}
return beforeStart;
}3.7 判断是否为回文链表。
提示
1、找到链表的中间节点；
2、将中间节点后面的节点反转；
3、头节点的值与最后一个节点的值进行比较，然后头节点往后，最后一个节点往前。
注意此题需要区分链表的节点数，如果是奇数比较好判断，但如果是偶数，需要考虑另一个判断条件。
奇数情况下：
偶数情况下：
判断条件是 fast.next = slow; 不能是 slow.next = fast;
且该判断条件前提是两者的数据是相等的，因此判断顺序很重要。
public boolean chkPalindrome(){ // 判断是否是回文链表
if(head == null){
return true;
}
// 1、找到中间节点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 2、反转
ListNode cur = slow.next;
while(cur != null){
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
// 3、判断是否是回文
while(head != slow){
if (head.val != slow.val){
return false;
}
// 如果链表是偶数的话，应该是下面的判断条件
// 前提是两个val值是相等的
if (head.next == slow){ // 注意是head的下一个节点是slow才对，因为slow的下一个节点回到了slow后面了。
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}3.8 输入两个链表，找出它们的公共节点。
public SingleLinkedList.ListNode getIntersectionNode
(SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) { // 两链表是否相交
SingleLinkedList.ListNode pLong = headA; // 假设链表A的长度比链表B的长
SingleLinkedList.ListNode pShort = headB;
int lenA = 0; // 链表A的长度
int lenB = 0; // 链表B的长度
while (pLong != null){
lenA++;
pLong = pLong.next;
}
while (pShort != null){
lenB++;
pShort = pShort.next;
}
// 因为在计算长度时改变了两个值，因此要从新定义
pLong = headA;
pShort = headB;
// 计算两个链表长度的差值
int len = lenA - lenB;
if (len < 0){ // 如果len为负数，说明lenB大于lenA，规定pLong一定指向长的链表
pLong = headB;
pShort = headA;
len = lenB - lenA; // 记住要把差值换成正数
}
// 长的链表先走len步
while (len != 0){
pLong = pLong.next;
len--;
}
// 两个引用同时走，知道它们相遇
while (pLong != pShort){
pLong = pLong.next;
pShort = pShort.next;
}
if (pLong == null){
return null; // 说明没有相交
}
return pLong;
}测试：
public static void creatIntersect
(SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB){ // 自己实现相交
headA.next.next = headB.next.next.next;
}
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addFirst(5);
linkedList.addLast(1);
linkedList.addLast(8);
linkedList.addLast(4);
linkedList.addLast(5);
SingleLinkedList linkedList2 = new SingleLinkedList();
linkedList2.addFirst(4);
linkedList2.addLast(1);
linkedList2.addLast(6);
linkedList2.addLast(8);
linkedList2.addLast(4);
linkedList2.addLast(5);
creatIntersect(linkedList.head, linkedList2.head);
SingleLinkedList.ListNode ret = getIntersectionNode(linkedList.head, linkedList2.head);
System.out.println(ret.val);
}3.9 判断链表中是否有环。
* 进阶：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
public boolean hasCycle(){ // 判断当前链表是否有环
if (head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
return true;
}
}
return false;
}
public void creatLoop(){ // 创建环
ListNode cur = head;
while (cur.next != null){
cur = cur.next;
}
cur.next = head.next.next.next;
}
public ListNode detectCycle() { // 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
ListNode fast = head;
ListNode slow = head;
while( fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast == null || fast.next == null){
return null; // 说明没有环
}
slow = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}测试类：
public class TestSingle {
public static void main(String[] args) {
// 测试返回链表开始入环的第一个节点。
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addFirst(5);
linkedList.addLast(1);
linkedList.addLast(8);
linkedList.addLast(4);
linkedList.addLast(5);
linkedList.creatLoop();
System.out.println(linkedList.hasCycle());
SingleLinkedList.ListNode ret = linkedList.detectCycle();
System.out.println(ret.val);
}
}