链表
单链表
单链表的结构与创建
结构
单链表具有表头，数据和指针（指向下一元素）
代码
public class SingleLinkList {
//创建头指针
private Node head = null;
//链表格式
private class Node {
//存储内容
int element;
Node next;
public Node(int element, Node next) {
this.element = element;
this.next = next;
}
}
}
头插
原理
先创建一个数据块，将链表块的next指针指向head连接的内容，再将head赋值为链表块
代码
public void addFirst(int element) {
//创建数据块，先将头指针连接的内容接到插入元素上，再将插入元素赋值给头指针
head = new Node(element, head);
// Node first = head;
// head = first
}
尾插
原理
尾插的原理比较简单，直接让最后一个元素的next指针指向刚创建的元素，但是链表不是数组，无法从下标直接调用到最后元素，所以只能采取遍历的方法，移动到最后一个元素，再进行赋值。
代码
尾部赋值
public void addLast(int element) {
//判断链表是否为空
// if (head == null) {
// addFirst(element);
// } else {//不为空，调用遍历，查找最后一个元素
// Node last = traversal();
// last.next = new Node(element, null);
// }
Node last = traversalLast();
// Node last = recursion(head);
if (last == null) {
addFirst(element);
return;
}
last.next = new Node(element, null);
}
for循环寻找Last节点
private Node traversalLast() {
if (head == null) {
return null;
}
Node point;
/*
这里的写的是point.next != null而不是point != null的原因是：
point的话即使他是最后一个他也会再往下运行一次,所以此时point指向的是空指针
*/
for (point = head; point.next != null; point = point.next) {
}
return point;
}
递归寻找Last节点
private Node recursion(Node node) {
//第一个条件判断链表是否为空，第二个判断是否有下一个节点
if(node == null || node.next == null) {
return node;
}
//无论递归多少次，最后return的一定是if语句中return的node
return recursion(node.next);
}
头删
原理
头删即直接将头节点指向第一节点的next节点，而头节点本就等于第一节点，所以头节点直接指向头节点的next节点
代码
public void removeFirst() {
if (head == null) {
System.out.println("头指针为空！");
return;
}
head = head.next;
}
查找删除
原理
通过遍历查找待删除的索引的前一个节点，将前一个节点的next值赋值为待删除节点的next值
代码
public void remove(int index) {
Node prev = searchIndex(index - 1);
// Node prev = recursionIndex(index - 1, 0, head);
Node removed = prev.next;
prev.next = removed.next;
}
//递归查找索引
private Node recursionIndex(int index, int i, Node point) {
if(index == i){
return point;
}else if(point == null){
return null;
}
i++;
return recursionIndex(index,i,point.next);
}
//for循环查找索引
private Node searchIndex(int index) {
int i = 0;
Node point;
for (point = head; point != null; point = point.next, i++) {
if (i == index) {
//找到了返回目标节点
return point;
}
}
return null;//没有找到
}
一遍删除完所有的相同值
思路
创建前后节点prev与rem，判断rem的element与val是否相同，如果相同就让prev.next = rem.next，然后rem = rem.next（节点向后移一位。如果没找到，prev和rem都向后移一位，也就可以写为prev = rem； rem = rem.next;
代码
public void lastingRemove(int val) {
Node prev = head;
Node rem = head.next;
while (rem != null) {
if (rem.element == val) {
prev.next = rem.next;
rem = rem.next;
} else {
prev = rem;
rem = rem.next;
}
}
if (head.element == val) {
head = head.next;
}
}
倒序排列链表
思路
使用三指针，先将new一个新的节点cur，获取head后面的一个节点，然后再创建一个节点p，记录cur之后的节点。这时候将head节点的next置空，然后将cur节点插如到head节点的前面，再将head赋值为cur，成为新的头节点（头插）。
代码
public void displaceElement() {
Node cur = head.next;
head.next = null;
Node p = cur.next;
//注意不是p.next否则会漏掉最后一个元素
while (p != null) {
p = cur.next;
cur.next = head;
head = cur;
cur = p;
}
}
快慢指针—输出节点中间数值
思路
创建两个指针，快指针一次位移两个节点，慢指针一次位移一个节点。当快指针到终点的时候，慢指针刚好在链表的中间节点（奇数为中间，偶数为中间的右节点）。
代码
//快慢指针，输出一个链表的中间值，如果是偶数的话就输出右边的值
public void outPutMiddleNode() {
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
System.out.println(slow.element);
}
快慢指针—输出指定倒数第K个节点的element
思路
通过快慢指针，先将fast指针向后移动k-1个节点，然后再将fast、slow指针同时移动，这样等fast指针结束的时候，slow指针就指在倒数第K个节点上。
代码
//快慢指针,输出倒数第K个节点
public void outPutBottomKTh(int k) {
if (k == 0) {
System.out.println("非法输入");
return;
}
Node fast = head;
Node slow = head;
while (k - 1 != 0) {
fast = fast.next;
if (fast == null) {
System.out.println("非法输入");
return;
}
k--;
}
while(fast.next != null) {
slow = slow.next;
fast = fast.next;
}
System.out.println(slow.element);
}
删除倒数第n个节点,并返回链表
思路
删除倒数第n个节点和上题使用的思路是相同的——快慢指针，但是写法有点区别，因为这里如果删除的是头节点的话，还需要特殊处理。所以我们需要创建一个标枪节点。
还是创建双节点fast和slow，让fast = head;slow = mark;这样位移的时候fast和slow中间可以始终差n个节点，当fast == null时，slow.next就是待删除的节点，令slow.next = slow.next.next即可。
此时如果只有一个节点的话，n = 1，这时fast往前走一步就为null，所以slow.next = slow.next.next (null)。
代码
public Node removeNthFromEnd(int n) {
Node mark = new Node(0, head);
Node fast = head;
Node slow = mark;
while(n != 0) {
fast = fast.next;
n--;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return mark.next;
}
链表的合并
思路
创建一个标枪指针newhead，再创建一个移动指针tmp，创建循环将head1和head2的元素拿来对比，将小的赋值给tmp，然后向下移动一个节点，当head1或者head2为空的时候，就说明有一个链表已经插入完毕，只需要将剩下的链表的head直接赋值给tmp.next即可。
图一
如上图，创建一个标枪指针newhead和一个移动指针tmp，下面就是比较head1的第一个Node和head2第一个Node，head1的element比head2的小，所以将head1赋值给tmp
图二
图二将head1赋值给tmp之后，head1 = head1.next; tmp = tmp.next;下面就在进行比较。
图三
图三是相同的，将head2的节点赋值给tmp.next;直到图四执行完毕。
图四
代码
public void CombineLinkList(SingleLinkList singleLinkList1, SingleLinkList singleLinkList2) {
Node head1 = singleLinkList1.head;
Node head2 = singleLinkList2.head;
if (head1 == null && head2 == null) {
System.out.println("双链表为空！");
return;
}
Node newhead =new Node(0,null);
Node tmp = newhead;
while(head1 != null && head2 != null ) {
if (head1.element
