前言
学习数据结构最好有C语言的基础，学过C语言的指针再去学数据结构会很容易
推荐书籍：CPrimerPlus、大话数据结构
资源
刷题网站
画图软件
OneNote
笔记软件
Typoral
链表理论基础
链表的类型
什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链接的入口节点称为链表的头结点也就是head。
单链表
上面这种形式就是单链表
双链表
单链表中的节点只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
如图所示：
循环链表
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
链表的存储方式
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。分配机制取决于操作系统的内存管理。
链表的定义
下面这个是C/C++的定义
// 单链表 struct ListNode { int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数 };
我们在Java中怎么定义呢？
其实都是差不多的，我们通过一个一个的对象来进行模拟，首先我们需要定义一个类，这是对象的模板
package com.sequenceTable.linkedlist1; public class ListNode { public int val; // 节点上存储的元素 public ListNode next; //指向下一个节点 public ListNode() { } public ListNode(int val) { this.val = val; } @Override public String toString() { return "ListNode{" + "val=" + val + '}'; } }
删除节点
删除节点D，很简单如图所示，把原本指向D节点的指针(对象的引用)指向E节点即可删除D节点了~
Java中有垃圾回收机制，D节点没有被引用就会被回收
添加节点
可以看出链表的增添和删除都是O(1)O(1)O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)O(n)O(n)。
链表和数据特性对比
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
移除链表元素
题意：删除链表中等于给定值 val 的所 有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
思路
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点
当然如果使用java ，python的话就不用手动管理内存了。
链表操作的两种方式：
- 直接使用原来的链表来进行删除操作。
- 设置一个虚拟头结点在进行删除操作。
来看第一种操作：直接使用原来的链表来进行移除。
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
之后在内存中删掉即可
这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。
那么可不可以 以一种统一的逻辑来移除 链表的节点呢。
其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。
这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。
这样是不是就可以使用和移除链表其他节点的方式统一了呢？
来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。
最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点
这个题其实一想就能想到用迭代的方式即可，一直往后找，找到后改变指向，没有找到继续后移，只需注意一个特殊情况，就是目标值为头结点的时候，所以我们定义的时候直接来个虚拟的结点。这样就可以匹配这种情况
java代码如下：
package com.sequenceTable.linkedlist1; public class removelinkedlistelements { public ListNode removeElements(ListNode head,int val){ // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作 //dummy也就是虚拟的意思 ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; //判断当前结点的后继结点是否为null while (prev.next != null){ //如果当前结点后继节点的值与给定的val相等 //则需将其后继结点删除 if (prev.next.val == val){ prev.next = prev.next.next; }else { // 如果当前结点的后继结点的值与给定值不相等 // 则当前结点需要保留，因此prev向前移动一个位置 prev = prev.next; } } // 最终返回的是删除后的头结点 return dummy.next; } }
设计链表
思路
这一章节，java不太好理解
如果没有基础，先看C-PrimerPlus和大话数据结构
最后在推荐尚硅谷的数据结构与算法课程，一定是这个顺序！
没有什么拐弯的地方，就是你熟悉链表了，知道CRUD指针是怎么变的了就能写出来
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
删除节点指针的变化如下：
添加链表节点指针的变化如下：
package com.caq.linkList; public class MyLinkedList { int size; ListNode head; //初始化链表 public MyLinkedList() { size = 0; head = new ListNode(0); } //获取第index个节点的数值 public int get(int index) { //如果index非法，返回-1 if (index < 0 || index >= size) { return -1; } ListNode currentNode = head; //包含一个虚拟头节点，所以查找第 index+1 个节点 for (int i = 0; i <= index; i++) { currentNode = currentNode.next; } return currentNode.val; } //在链表最前面插入一个节点 public void addAtHead(int val) { addAtIndex(0, val); } //在链表的最后插入一个节点 public void addAtTail(int val) { addAtIndex(size, val); } // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。 // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点 // 如果 index 大于链表的长度，则返回空 public void addAtIndex(int index, int val) { if (index > size) { return; } if (index < 0) { index = 0; } size++; //找到要插入节点的前驱 ListNode pred = head; for (int i = 0; i < index; i++) { pred = pred.next; } ListNode toAdd = new ListNode(val); toAdd.next = pred.next; pred.next = toAdd; } //删除第index个节点 public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } size--; ListNode pred = head; for (int i = 0; i < index; i++) { pred = pred.next; } pred.next = pred.next.next; } }
反转链表
思路
改变链表的next指针的指向，直接将链表反转
这动画都绝了好吗，真是一看就知道啥意思！！！
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点
初始情况如下图所示：
package com.caq.linkList; public class SolutionReverseList { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; ListNode temp = null; while (cur != null) { temp = cur.next;// 保存下一个节点 cur.next = prev; prev = cur; cur = temp; } return prev; } }
temp = cur.next
这里的意思是将cur.next指向temp，也就是将temp指向第二个结点
作用是为了后序的反转
递归法
和双指针类似
public ListNode reverseList(ListNode head) { return reverse(null, head); } private ListNode reverse(ListNode prev, ListNode cur) { if (cur == null) { return prev; } ListNode temp = null; temp = cur.next;// 先保存下一个节点 cur.next = prev;// 反转 // 更新prev、cur位置 // prev = cur; // cur = temp; return reverse(cur, temp); }
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
这道题目正常模拟就可以了。
接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序
初始时，cur指向虚拟头结点，然后进行如下三步：
一定要自己动手去画这个过程
递归
public ListNode swapPairs(ListNode head) { // base case 退出提交 if(head == null || head.next == null) return head; // 获取当前节点的下一个节点 ListNode next = head.next; // 进行递归 ListNode newNode = swapPairs(next.next); // 这里进行交换 next.next = head; head.next = newNode; return next; }
递归的过程如下：
虚拟头节点
public ListNode swapPairs(ListNode head) { ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode prev = dummyNode; while (prev.next != null && prev.next.next != null) { ListNode temp = head.next.next; // 缓存 next prev.next = head.next; // 将 prev 的 next 改为 head 的 next head.next.next = head; // 将 head.next(prev.next) 的next，指向 head head.next = temp; // 将head 的 next 接上缓存的temp prev = head; // 步进1位 head = head.next; // 步进1位 } return dummyNode.next; }
删除链表的倒数第N个节点
思路
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
图解
1、初始情况
2、fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
3、fast和slow同时移动，直到fast指向末尾
4、删除slow指向的下一个节点
自己想的确也想不到可以这样，先记下熟悉思路！
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode slow = dummy; ListNode fast = dummy; while (n-- > 0) { fast = fast.next; } // 记住 待删除节点slow 的上一节点 ListNode prev = null; while (fast != null) { prev = slow; slow = slow.next; fast = fast.next; } // 上一节点的next指针绕过 待删除节点slow 直接指向slow的下一节点 prev.next = slow.next; return dummy.next; }
链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
简单来说，就是求两个链表交点节点的指针,交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。
public class LinkedListCrossing { public ListNode getNewLinkedListCrossing(ListNode headA, ListNode headB){ ListNode curA = headA; ListNode curB = headB; int lenA = 0, lenB = 0; while (curA != null){ lenA++; curA = curA.next; } while (curB != null) { // 求链表B的长度 lenB++; curB = curB.next; } curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { //1. swap (lenA, lenB); int tmpLen = lenA; lenA = lenB; lenB = tmpLen; //2. swap (curA, curB); ListNode tmpNode = curA; curA = curB; curB = tmpNode; } // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap-- > 0) { curA = curA.next; } // 遍历curA 和 curB，遇到相同则直接返回 while (curA != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; } }
curA = headA;curB = headB;
因为前面代码通过指针遍历，获取链表长度计算lenA,lenB
后面又写这行代码意思是让指针返回原位置
其他不懂的地方，代码注释中标注了
环形链表
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
题目含义
题目是什么意思呢，其实多举几个例子就能明白了
如果是多个节点的单向链表，都是一样，入环点就是第二个节点
如果链表是下面这样，那么入环点就是第四个节点
思路
完成这道题就两步
- 判断链表是否有环
- 找到这个环的入口
判断链表是否有环
fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
找到这个环的入口
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) {// 有环 ListNode index1 = fast; ListNode index2 = head; // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口 while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }
总结
- 链表的种类主要为：单链表，双链表，循环链表
- 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
