数据结构青铜到王者第四话---LinkedList与链表（1）
目录
一、链表
1、链表的概念及结构
2、链表的实现
二、常见的链表题目练习
1、删除链表中等于给定值 val 的所有结点。
2、反转一个单链表。
3、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
4、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
5、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
前面我们已经熟悉了ArrayList的使用，与此同时还进行了简单的模拟实现。通过查看源代码我们可以知道，ArrayList的底层是使用数组来进行元素的存储的：
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...// 数组：用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}}// ...
}由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，也就是链表结构。
一、链表
1、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
#注：
（1）从上图可以看出，链表结构在逻辑上是连续的，但在物理上不一定连续
（2）现实中的结点一般都是从堆上申请出来的
（3）从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
实际中的链表结构有很多种，以下的情况组合起来就有8种链表结构：
（1）单向或者双向
（2）带头或者不带头
（3）循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种就可以了:
（1）无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
（2）无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2、链表的实现
// 无头单向非循环链表实现public class SingleLinkedList {//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){int len = size();if(index < 0 || index > len) {System.out.println("index位置不合法");return;}if(index == 0) {addFirst(data);return;}if(index == len) {addLast(data);return;}//中间插入ListNode cur = head;while (index - 1 != 0) {cur = cur.next;index--;}ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode cur = findNodeOfKey(key);if(cur == null) {return;}ListNode del = cur.next;cur.next = del.next;}private ListNode findNodeOfKey(int key) {ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}//删除所有值为key的节点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;}}//得到单链表的长度public int size(){int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}return len; }public void clear() {ListNode cur = head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}二、常见的链表题目练习
对于链表而言，懂得是怎样实现的之后最好的方法也就是去做习题进行练习！！！
1、删除链表中等于给定值 val 的所有结点。
（203. 移除链表元素 - 力扣（LeetCode））
对于这个题，很简单，但是要记得考虑链表为空的情况！！！
然后去比较即可，若是相等就把其前一个结点的地址改为它后一个结点的地址，直接将相等的跳过即可（如第2个结点，就让第1个结点去存储第3个结点的地址）
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}head.next = removeElements(head.next, val);return head.val == val ? head.next : head;}
}2、反转一个单链表。
（206. 反转链表 - 力扣（LeetCode））
这一题给了我们头结点（head），我们就可以依次找到后面的所有结点，将我们所找到的结点依次进行头插入就可以完成（因为给了1，我们可以依次得到2345，但是最终要得到54321，所以进行头插入）
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}3、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
（876. 链表的中间结点 - 力扣（LeetCode））
这里，我们需要用到一个新的解题方式----快慢指针（就是用两个指针同时出发）
在这个题里面要找到中间结点，那么就用两个指针，快指针一次走两步，慢指针一次走一步，那么当快指针走到末尾无法再走时，慢指针恰好走到中间（奇偶情况如下图）
class Solution {public ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}4、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
（21. 合并两个有序链表 - 力扣（LeetCode））
这里说到有序链表，所以可以先建立一个新的链表，再将两个旧链表从头依次开始比较，谁小谁就尾插进新链表，而其所在的链表就要拿出下一个结点进行下一轮的比较，直到一方为空（即比完了），那么让非空的链表将剩余部分尾插到新链表，再返回新链表头结点的下一个结点即可
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 == null ? l2 : l1;return prehead.next;}
}5、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
（链表分割_牛客题霸_牛客网）
创建四个空表，两两一组，先比较与x的大小关系，（bs是小于x的头记录，be记录小于x的尾），第一次找到大于等于或小于的结点时都是先同时等于头结点，然后e依次去记录后面的，直到遍历完整个链表。这时要考虑小于x的链表为空的情况，若是为空直接返回大于x的链表，否则把小于x的链表的尾连接上大于x的链表的头（并且将大于x的链表尾结点置为null）
public ListNode partition(int x) {// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = head;while (cur != null) {if(cur.val < x) {//第一次插入if(bs == null) {bs = be = cur;}else {be.next = cur;be = be.next;}}else {if(as == null) {as = ae = cur;}else {ae.next = cur;ae = ae.next;}}cur = cur.next;}if(bs == null) {return as;}be.next = as;//不管第二部分是否最后一个节点为空 都手动置为空if(as != null) {ae.next = null;}return bs;}由于内容较多，会分为多篇讲解，预知后续内容，请看后续博客！！！