外观
链表
link : 代码随想录链表部分
1. 链表介绍
1.1 链表的分类
单链表
链表：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
图示： 
双链表
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
图示： 
循环链表
循环链表，就是链表首尾相连。
循环链表可以用来解决 约瑟夫环问题。
1.2 链表的存储方式
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
即 数组在内存中是连续分布的，链表在内存中不是连续分布的
这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。
1.3 链表的实现（代码实现）
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}一定要自己定义构造函数, 从而便于在初始化的时候为数据域赋值
1.4 链表的操作
删除节点
删除节点 D ：
将C节点的next指针 指向E节点就可以了
添加节点
添加节点 F ：
链表的增添和删除都是O(1)操作，也不会影响到其他节点。 但是如果删除最后一个节点，就需要从头开始查找，复杂度为
1.5 性能分析
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
2. 移除链表元素
link : LeetCode 203
思考：
以链表 1 4 2 4 来举例，移除元素4：
特殊情况：移除头节点
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
移除头节点的两种方式：
- 直接使用原来的链表来进行删除操作。
- 设置一个虚拟头结点在进行删除操作
方法一：直接使用原来的链表来进行删除操作。(将头结点向后移动一位，这样就从链表中移除了一个头结点)
这种情况下，将移除头节点作为一种特殊的情况，单独写一段代码来处理
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 直接在原链表进行操作
// 判断头节点是否满足要求
// 必须使用while, 从而保证得到的 链表 头节点不满足要求
// 比如 1 1 1 1 2, val=1 的情况
while(head != null && head.val == val){
head = head.next;
}
// 判断非头节点
// 非头节点的删除是通过前一个节点来完成
ListNode newNode = head;
// 需要判断 newNode是否为空
// 比如 1 1 1 1 1, val = 1, 那么 newNode=null
while(newNode != null && newNode.next != null){
if (newNode.next.val == val){
newNode.next = newNode.next.next;
}else{
newNode = newNode.next;
}
}
return head;
}
}方法二：设置一个虚拟头结点在进行删除操作 (这样原链表的所有节点就都可以按照统一的方式进行移除了)
最后在题目中，return 头结点的时候，别忘了 return virtualHead.next;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 设置一个虚拟节点, 从而使得删除头节点和删除非头节点都是通过前面的节点实现
ListNode virtualHead = new ListNode(-1, head);
ListNode newNode = virtualHead;
while(newNode.next != null){
if (newNode.next.val == val)
newNode.next = newNode.next.next;
else newNode = newNode.next;
}
return virtualHead.next;
}
}3. 设计链表
link : LeetCode 707
思考：
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
链表操作的两种方式：
- 直接使用原来的链表进行操作
- 设置一个虚拟头节点进行操作
采用 设置一个虚拟头节点的方法：
// 定义链表节点类
class ListNode{
int val;
ListNode next;
public ListNode(){}
public ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
// 链表的虚拟头节点
ListNode virtualHead;
// size: 链表的元素个数
int size;
// 初始化链表
// 此处是初始化一个虚拟的头节点
public MyLinkedList() {
this.virtualHead = new ListNode(-1);
this.size = 0;
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
// 因为index是从0开始, 所以index的有效范围为 [0, size-1]
public int get(int index) {
if (index >= size || index < 0) return -1;
ListNode tempNode = virtualHead;
int res;
// 因为包含了虚拟节点,所以进行查找的时候需要查找到 第 index+1 个节点
for (int i=0; i <= index; i++){
tempNode = tempNode.next;
}
res = tempNode.val;
return res;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
public void addAtHead(int val) {
ListNode newHeadNode = new ListNode(val);
// 因为是在链表的最前面插入一个节点, 所以下一个节点是原链表的头节点
newHeadNode.next = this.virtualHead.next;
this.virtualHead.next = newHeadNode;
// 插入一个节点, 链表的长度加一
this.size++;
}
// 在链表最后面添加一个节点
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode tempNode = this.virtualHead;
while(tempNode.next != null)
tempNode = tempNode.next;
tempNode.next = newNode;
// 链表节点加一
this.size++;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
public void addAtIndex(int index, int val) {
// 在头部插入节点
if (index <= 0){
this.addAtHead(val);
}
else if(index == size){
this.addAtTail(val);
}else if (index > size){
return;
}else{
ListNode newNode = new ListNode(val);
ListNode tempNode = this.virtualHead;
// 因为是插入到 链表中下标为index的节点之前, 所以需要找到该节点前面的 节点
// 而因为链表中有虚拟头节点, 所以相当于需要找到第 index - 1 + 1个节点
for (int i=0; i<index; i++)
tempNode = tempNode.next;
// 找到前面的节点
newNode.next = tempNode.next;
tempNode.next = newNode;
size++;
}
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
public void deleteAtIndex(int index) {
if (index >= 0 && index < size){
ListNode tempNode = this.virtualHead;
// 找到下标为 index 的前面的节点
for (int i=0; i<index; i++)
tempNode = tempNode.next;
// 进行删除
tempNode.next = tempNode.next.next;
size--;
}else return;
}
}4. 反转链表
link: LeetCode 206
思考：
只需要改变链表的 next 指针的指向，就可以直接将链表反转，从而不用定义一个新的链表
双指针法：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
之后 需要pre 和 cur 都向前走一位
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 使用双指针, 一个pre, 一个curNode, 一个指向当前节点之前的节点, 一个指向当前节点
ListNode pre = null;
// 当前的节点
// 需要当前节点遍历整个链表
ListNode curNode = head;
// 当前节点的下一个节点
ListNode tempNode;
while(curNode != null){
tempNode = curNode.next;
curNode.next = pre; // 改变当前节点的指向
// 更新 pre 和 curNode, 都向前走一位
pre = curNode;
curNode = tempNode;
}
// 遍历结束后, pre正好指向最后一个节点, curNode = null
// 因为改变了指针的指向, 所以最后的节点变成了头节点
return pre;
}
}5. 两两交换链表中的节点
link: LeetCode 24
思考：
因为需要进行节点交换，而不是单纯更改节点内的值，因此需要改变节点的指针
图示:
交换过程：
- 初始的时候，cur指针指向虚拟的头节点（其实可以将cur看成虚拟头节点）
对节点的操作，需要前面的节点才能找到，因此为了保证对头节点的操作逻辑和与其他节点相同，涉及到链表的节点操作都用虚拟头节点
tmp1 = cur.next
tmp2 = cur.next.next.next
cur.next = cur.next.next // 指向 cur->2
cur.next.next = tmp // 2->1
cur.next.next.next = tmp2 // 1->3
// 更新cur, 向前移动两位
cur = cur.next.next // cur指向1号节点- 操作之后的链表
即： 
代码实现：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 使用虚拟头节点
ListNode virtualNode = new ListNode(-1, head);
// 定义当前节点, 一开始指向虚拟头节点, 从而保证处理头节点和其他节点采用相同的逻辑
ListNode curNode = virtualNode;
// 需要进行交换的是 curNode.next 和 curNode.next.next
// 因此需要保证两者都不为null
while (curNode.next != null && curNode.next.next!=null){
ListNode tmp1 = curNode.next;
// 要保证链表的连接
ListNode tmp2 = curNode.next.next.next;
curNode.next = curNode.next.next; // cur->2
curNode.next.next = tmp1; // 2->1
curNode.next.next.next = tmp2; // 1->3
// 交换之后, cur 向前移动两位, 移动到 下一组需要交换的两个节点的前面一个节点
curNode = curNode.next.next;
}
return virtualNode.next;
}
}6. 删除链表的倒数第N个节点
link : LeetCode 19
思考： 要删除倒数第N个节点, 那么必须找到该节点前面的节点
使用双指针：双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路：
为了保证操作头节点的逻辑和操作其他节点相同，使用虚拟头节点
定义fast指针和slow指针，初始值为虚拟头结点，如图：
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：(移动n步也可以, 代码实现是按照移动n步)
- fast和slow同时移动，直到fast指向末尾，如题：
- 删除slow指向的下一个节点，如图：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 定义一个虚拟头节点, 从而保证处理头节点的逻辑和处理其他节点相同
ListNode virtualNode = new ListNode(-1, head);
// 使用双指针, 先让fastNode向前移动n步, 然后两者一块移动
// 当 fast指针 指向链表最后一个元素, slow指针指向目标节点的前一个节点
ListNode slowNode = virtualNode;
ListNode fastNode = virtualNode;
for (int i=0; i<n; i++){
fastNode = fastNode.next;
}
// 两者同时移动
// 当fastNode指向最后的一个元素跳出循环
while(fastNode.next != null){
slowNode = slowNode.next;
fastNode = fastNode.next;
}
// 删除目标元素
slowNode.next = slowNode.next.next;
return virtualNode.next;
}
}7. 链表相交
link: LeetCode 160
思考：
题目即为求 两个链表交点的节点的指针（即 c1），但是交点不是数值相等, 而是指针相等, 比如下面的图是： 
很明显，相交的节点是 “8”， 而不是 “1”
思路：
首先求出两个链表的长度，然后求出两个链表的长度的差值，然后将指向长度比较长的链表的指针先移动
比如下面图示：
如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
从而比较 curA和curB是否相等, 如果不相等的话，继续同时向后移动
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
// 求出两个链表的长度
while(curA != null){
curA = curA.next;
lenA++;
}
while(curB != null){
curB = curB.next;
lenB++;
}
curA = headA;
curB = headB;
// 保证 A 链表是长度比较长的链表
// 如果不是则交换, 从而保证下面的逻辑通用
if (lenB > lenA){
int temp = lenA;
lenA = lenB;
lenB = temp;
ListNode tempNode = curA;
curA = curB;
curB = tempNode;
}
// 下面首先长度比较长的链表先移动两者的差值
int gap = lenA - lenB;
while(gap-- > 0){
curA = curA.next;
}
// 判断curA和curB是否相等
while(curA != null){
if (curA == curB) return curA;
curA = curA.next;
curB = curB.next;
}
return null;
}
}8. 环形链表 (重点看)
link: LeetCode 142
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思考：
link : 代码随想录 环形链表
video:
考察两方面的内容：
- 判断链表是否有环（快慢双指针）
- 如果有环，如何寻找环的入口处
判断链表是否有环：
使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
fast 必须是移动两个节点，slow 必须是移动一个节点，这样快指针相当于以 每次多移动一个节点的速度追赶慢指针，如果有环，则必定能够追赶上。 如果fast每次移动三个节点，slow每次移动一个节点，这样快指针相当于以每次多移动两个节点的速度追赶慢指针，那么有可能会跳过慢指针
fast 和 slow的移动图示：
如果链表中有环，如何寻找环的入口：
假设从头节点到环形入口节点 的节点数是 , 环形入口节点到 fast与slow相遇节点的节点书为 , 从相遇节点啊到环形入口节点 的节点数为
fast与slow 相遇的时候, slow 走过的节点数为 , fast走过的节点数为
slow 必定是在进入环中 第一圈的时候被fast遇到 fast 必定是在环中走了至少一圈，然后遇到了slow， 表示fast在环中走的圈数
因为fast每一步走两个节点, slow每一步走一个节点，所以相遇的时候 根据走过的路径距离形成一个等式：
左右两边同时消去 , 并且把 单独放在左边：
此时看不出什么等量关系，从 中提取出来一个
其中 是环形中的节点数目，如果 , 即fast 在环形中走一圈后, 与 slow 相遇, 那么
即：从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。（另一个等量关系）
当然，也有可以 fast 在环形中走了 若干圈(即 n!=1), 与 slow 相遇, 但是即使是这样, 从 头节点出发一个指针index1，从相遇节点也出发一个指针index2，这两个指针每次只走一个节点，即使 index2 在环中走了若干圈，但是最后仍然会和 index1 相遇
index1 = head;
while (index1 != index2){
index1 = index1.next
index2 = index2.next
size++;
}
// 循环必定会打破, 打破循环的时候 index1=index2 就是环的入口代码实现：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// 1. 使用快慢指针找到相遇的地方
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
// 2. 寻找环的入口
ListNode index1 = head;
ListNode index2 = slow;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}