写链表代码是最考验逻辑思维能力的，指针来回指，指着指着就指迷糊，在写代码之前先注意这么几个问题。
日志
2019年3月20日 查漏补缺，新增循环链表的实现
2019年3月18日 查漏补缺，新增双向链表的实现
问题1：什么是指针？
定义：
有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
举例：
最常见的指针代码应该是这个了，p->next=q。它的意思是说p 结点中的 next 指针存储了 q 结点的内存地址。
问题2：什么是指针丢失和内存泄漏？
在插入结点时，一定要注意操作的顺序。
因为操作不当的时候，很容易造成指针丢失。比如a ->b之间插入一个c，同时不注意的时候很容易这么写
//声明一个p;
p->next = c; // 将 p 的 next 指针指向 c 结点;
c->next = p->next; // 将 c 的结点的 next 指针指向 b 结点;
这就很容易让链表断成两半，造成指针丢失。正确的写法是将二三两行代码顺序换过来即可。
删除链表结点时，也一定要记得手动释放内存空间。
和插入一样，如果不及时释放内存空间，积少成多，很容易造成内存泄漏。
技巧：利用哨兵节点简化实现难度
哨兵节点主要是处理边界问题的，并不直接参与业务逻辑，当引入哨兵节点的时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。
练习：
以单链表为例，所有源码均已上传至github:链接
声明一个单链表类
public class Node {
public int data;
public Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}1.实现单链表，支持增删查操作
顺序插入
public void insertTail(int value) {
Node node = new Node(value, null);
if (head == null) {
head = node;
} else {
Node q = head;
// 找到最后next一个为不空节点并赋值
while (q.next != null) {
q = q.next;
}
// 注意，顺序不可反，否则链表就断开了
// 很精髓
node.next = q.next;
q.next = node;
}
}删除，难点就一行q.next = q.next.next;
public void deleteByNode(int value) {
if (head == null)
return;
Node p = head;
Node q = null;
// 从链表中找到要删除的value
while (p != null && p.data != value) {
q = p;
p = p.next;
}
if (p == null)
return;
if (q == null) {
head = head.next;
} else {
// 删除节点，其实就是把要删除的值prev节点指向他的next节点
// 很精髓
q.next = q.next.next;
}
}查询，分两个，一个是根据下标查询，一个是根据value查询
public Node findByIndex(int index) {
Node p = head;
int pos = 0;
while (p != null && pos != index) {
p = p.next;
++pos;
}
return p;
} public Node findByValue(int value) {
Node p = head;
while (p != null && p.data != value) {
p = p.next;
}
return p;
}测试结果：
2.单链表反转
该实现的思想是：从前往后反转各个结点的指针域的指向。
将当前节点cur的next节点 缓存到nextNode，然后更改当前节点指针指向上一结点prevNode。也就是说在反转当前结点指针指向前，先把当前结点的指针域用nextNode临时保存，以便下一次使用
public Node reverse(Node node) {
Node resNode = null;
Node prevNode = null;
Node curNode = node;
while (curNode != null) {
Node nextNode = curNode.next;
if (nextNode == null) {
resNode = curNode;
}
curNode.next = prevNode;
prevNode = curNode;
curNode = nextNode;
}
return resNode;
}测试结果：
3.链表中环的检测
该检测的核心思想是：快慢指针法。在这里，满指针每走一步，快指针走两步，可以用数学归纳法来考虑，首先，如果链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。那么
1：快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
2：快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
...
N：快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。
代码如下：
public boolean checkCircle(Node node) {
if (node == null)
return false;
// 快慢指针法
Node slow = node;
Node fast = node.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast)
return true;
}
return false;
}测试结果:
4.求链表的中间结点
该实现也是用到了快慢指针法。
代码如下：
public Node findMiddleByNode(Node node) {
if (node == null)
return null;
// 快慢指针法
Node fast = node.next;
Node slow = node;
// 快指针走完一圈，慢指针半圈
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}测试结果如下：
5.删除链表倒数第 n 个结点
该实现依旧用到了快慢指针法，不过和之前的有一点区别。以node长度为n，删倒数第k（k<n）个为例。首先，第一个while先计算如果正着删，需要让慢指针走几步，计算为n-k。第二个while循环则通过遍历快指针计算定位需要走n-k步,得到preNode。然后判断是否为空，不为空则常规方法删除。
public Node deleteLastKByNode(Node node, int k) {
// 快慢指针法
Node fast = node;
// 计数
int i = 1;
while (fast != null && i < k) {
fast = fast.next;
++i;
}
if (fast == null)
return node;
Node slow = node;
Node prevNode = null;
while (fast.next != null) {
fast = fast.next;
prevNode = slow;
slow = slow.next;
}
if (prevNode == null) {
node = node.next;
} else {
// 删除
prevNode.next = prevNode.next.next;
}
return node;
}测试结果:
6.两个有序的链表合并
该实现的思路是，首先比较两个有序链表，如果pNode为空，直接返回qNode，反之qNode为空，则返回pNode，然后比较p和q，将最小的节点赋值给resNode，同时将最小的节点向后移动一位。设置一个node指向resNode节点，用于方便连接其它节点，在继续比较p和q，同样选出小的那个节点，将该节点设为合并后的链表的第二个节点，用node.next表示该节点，一直重复上述过程，直到p和q有一个为null，然后再将不为null的节点放入新链表后即可。
public Node mergeNode(Node pNode, Node qNode) {
if (pNode == null)
return qNode;
if (qNode == null)
return pNode;
Node p = pNode;
Node q = qNode;
Node resNode = null;
if (p.data < q.data) {
resNode = p;
p = p.next;
} else {
resNode = q;
q = q.next;
}
Node node = resNode;
while (p != null && q != null) {
if (p.data < q.data) {
node.next = p;
p = p.next;
} else {
node.next = q;
q = q.next;
}
node = node.next;
}
if (p != null) {
node.next = p;
} else {
node.next = q;
}
return resNode;
}测试结果：
双向链表
双向链表类
package juejin.lc.linkedList;
/**
* 双向链表类
*/
public class DulNode {
/**
* 数据
*/
public int data;
/**
* 前驱节点
*/
public DulNode prev;
/**
* 后继节点
*/
public DulNode next;
private DulNode(){}
/**
* 有参构造方法
*
* @param data 数据
*/
public DulNode(int data) {
this.data = data;
}
}初始化
private DulNode head;
private DulNode tail;
private int count;
private DulLinkList() {
head = null;
tail = null;
count = 0;
}增
添加到链表头部
private void insertToHead(int data) {
DulNode dulNode = new DulNode(data);
if (count == 0) {
head = dulNode;
tail = dulNode;
} else {
DulNode prev = head;
prev.prev = dulNode;
dulNode.next = head;
head = dulNode;
}
++count;
}添加到链表尾部
private void insertToTail(int data) {
DulNode dulNode = new DulNode(data);
if (count == 0) {
head = dulNode;
tail = dulNode;
} else {
DulNode next = tail;
dulNode.prev = next;
next.next = dulNode;
tail = dulNode;
}
++count;
}添加到链表指定位置
private void insertByIndex(int index, int data) {
if (index > count) {//放入链表尾部
insertToTail(data);
} else {
DulNode resNode = selectByIndex(index);
if (null != resNode) {
System.out.println("根据index索引所得返回值为：" + resNode.data);
DulNode dulNode = new DulNode(data);
DulNode prev = resNode.prev;
prev.next = dulNode;
dulNode.prev = prev;
dulNode.next = resNode;
resNode.prev = dulNode;
}
}
++count;
}删
删除链表头部
private DulNode deleteHead() {
DulNode p = head;
if (count > 0) {
head = head.next;
head.prev = null;
--count;
}
return p;
}删除链表尾部
private DulNode deleteTail() {
DulNode q = tail;
if (count > 0) {
tail = tail.prev;
tail.next = null;
--count;
}
return q;
}删除链表指定位置
private void deleteByIndex(int index) {
if (index > count)
return;
//删除这边加了个小技巧，如果是链表头部或者尾部，直接删除，中间值开始查找
if (index == 0) {
head = head.next;
head.prev = null;
} else if (index == count - 1) {
tail = tail.prev;
tail.next = null;
} else {
DulNode resNode = selectByIndex(index);
if (null != resNode) {
System.out.println("要删除的元素为：" + resNode.data);
DulNode prev = resNode.prev;
DulNode next = resNode.next;
prev.next = next;
next.prev = prev;
resNode.prev = null;
resNode.next = null;
}
}
--count;
}查
根据指定索引获取节点
private DulNode selectByIndex(int index) {
if (index > count) return null;
int num = 0;
DulNode dulNode = head;
while (num < index) {
dulNode = dulNode.next;
++num;
}
return dulNode;
}根据指定节点获取下标
private int indexOf(int data) {
int num = 0;
DulNode dulNode = head;
while (num < count && null != dulNode) {
if (data == dulNode.data) {
return num;
}
dulNode = dulNode.next;
++num;
}
return -1;
}测试代码：
DulLinkList dulLinkList = new DulLinkList();
dulLinkList.insertToHead(3);
dulLinkList.insertToHead(2);
dulLinkList.insertToHead(1);
dulLinkList.insertToTail(5);
dulLinkList.insertToTail(6);
dulLinkList.insertToTail(7);
dulLinkList.insertToTail(8);
dulLinkList.insertToTail(9);
dulLinkList.printAll();
System.out.println("删除头部,并返回");
DulNode resHead = dulLinkList.deleteHead();
System.out.println("返回值：" + resHead.data);
dulLinkList.insertByIndex(3, 4);
dulLinkList.printAll();
System.out.println("删除尾部,并返回");
DulNode resTail = dulLinkList.deleteTail();
System.out.println("返回值：" + resTail.data);
dulLinkList.printAll();
int data = 5;
int res = dulLinkList.indexOf(data);
System.out.println("数据" + data + "的下标 " + (res != -1 ? res : "不存在"));
int delData = 5;
dulLinkList.deleteByIndex(delData);
dulLinkList.printAll();测试结果：
循环链表
初始化
/**
* 头结点
*/
private Node head;
/**
* 尾结点
*/
private Node tail;
/**
* 数据数量
*/
private int count;
/**
* 无参构造方法
*/
private CircleLinkList() {
head = null;
tail = null;
count = 0;
}插入头部
private void insertHead(int data) {
Node node = new Node(data, null);
if (count == 0) {
head = node;
tail = node;
} else {
node.next = head;
head = node;
tail.next = head;
}
++count;
}插入尾部
private void insertTail(int data) {
Node node = new Node(data, null);
if (count == 0) {
head = node;
tail = node;
} else {
tail.next = node;
node.next = head;
head = node;
}
++count;
}插入指定位置
private void insertByIndex(int index, int data) {
if (index > count) {
insertTail(data);
} else {
Node resNode = findByIndex(index);
if (null != resNode) {
System.out.println("返回节点的值:" + resNode.data);
resNode.next = new Node(data, resNode.next);
++count;
}
}
}删除
private void delete(int index) {
if (index > count) return;
if (index == 0) {
Node node = head;
head = head.next;
node.next = null;
tail.next = head;
} else if (index == count - 1) {
Node resNode = findByIndex(index);
if (null != resNode) {
Node node = tail;
tail = resNode;
node.next = null;
tail.next = head;
}
} else {
Node resNode = findByIndex(index - 1);//查找该节点的前一个节点
if (null != resNode) {
System.out.println("返回节点的值:" + resNode.data);
resNode.next = resNode.next.next;
}
}
--count;
}按索引查找
private Node findByIndex(int index) {
if (index > count) return null;
Node node = head;
int num = 0;
while (num < index) {
node = node.next;
++num;
}
return node;
}测试代码
public static void main(String[] args) {
CircleLinkList circleLinkList = new CircleLinkList();
circleLinkList.insertHead(3);
circleLinkList.insertHead(2);
circleLinkList.insertHead(1);
circleLinkList.insertTail(5);
circleLinkList.insertTail(6);
circleLinkList.insertTail(7);
circleLinkList.insertTail(8);
circleLinkList.insertByIndex(3,4);
circleLinkList.printAll();
LinkedListAlgo linkedListAlgo = new LinkedListAlgo();
boolean result = linkedListAlgo.checkCircle(circleLinkList.head);
System.out.println("检测环返回值：" + result);
circleLinkList.delete(1);
circleLinkList.printAll();
}测试结果
end
您的点赞和关注是对我最大的支持，谢谢！
