概念解释：
【线性表】：“线性存储结构”，一根线能串起来的数组，存储到物理空间之中。
数据要有相同的数据类型，元素之间的关系要是“一对一”关系
线性表和链表的是两种存储结构，“线式”和“链式”。
【前置节点】链表中某一个节点指向的前一个节点
【后继节点】与前置节点相对，链表中某一个节点指向的后一个节点
【图示】：线性表是不管逻辑上还是物理位置上都是以线性的方式罗列的，而链表在逻辑上是线性的，但是在物理结构上更多的是以一种引用的方式排列的。
【背景】
链表出现的背景是因为线性表要进行增删的时候，需要挪动其他相关的元素，而为了解决这个问题提出的链表结构在做增删操作时，增加最多只需要断开一条引用增加两条引用就可以了，删除则只需要打断两条引用增加一条引用即可。同时要做扩容操作时也相对较为高效简便。
【代码实现】
public class ListNode {String data;ListNode next;public ListNode(String data) {this.data = data;}public static ListNode arrayToListNode(String[] arr){if (arr.length == 0){return null;}//生成链表的根节点ListNode root = new ListNode(arr[0]);//先将根节点设置为前置节点ListNode pre = root;for (int i = 1; i < arr.length; i++) {ListNode node = new ListNode(arr[i]);//将前置节点的next指针指向当前节点，创建链接关系pre.next = node;//创建完链接关系后将当前节点更新为前直接点，以便于下一次循环创建接下来的链接关系pre = node;}return root;}}
【双链表】
【拓展】：
链表和数组的区别：链表的优点是实现了动态处理，不需要处理固定容量带来的问题。缺点则是失去了随机访问的能力。因此单链表的特点是增删快，查询慢；数组的特点是增删慢，查询快。
【双链表】：
单链表内只包含节点数据以及下一个节点的引用，而双链表则还包含上一个节点的引用。也就是说双链表包括
数据 + 前置指针 + 后置指针
添加元素：
删除元素：
JAVA经典实现：LinkedList
【查询方式】
如根据元素索引位置找到元素，如果在链表的前半段则从前往后遍历，如果在链表的后半段则从后往前遍历
【环形链表】
链表的尾部节点指向链表中的某一个节点元素，使链表形成一个环形结构。
/*** 给一个链表的pos索引位置处加入口节点使其形成环形链表* @param node* @param pos 代表尾节点的指向，链表中某个节点的索引位置（也就是环的入口）*/public static void toCycle(ListNode node,int pos){//记录遍历指针指向的当前位置的索引int cnt = 0;//环的入口处的节点ListNode cycleNode = null;while (true){//遍历到pos位置处后，将遍历到的节点赋值给cycleNodeif (cnt == pos){cycleNode = node;}//遍历到尾节点时，将尾节点的next指针指向cycleNodeif (node.next == null){node.next = cycleNode;return;}node = node.next;cnt++;}}
相关算法
一、输出链表中倒数第K个节点
解法①：总长度减去k再加1
第一次遍历，拿到链表长度相关数据n，第二次遍历将n-k+1作为遍历次数，拿到对应的第K个节点的Node
public static ListNode getKthFromEnd(ListNode head,int k){int n = 0;ListNode tmp = head;while (tmp.next != null){n++;tmp = tmp.next;}tmp = head;for (int i = 0; i < n - k + 1; i++) {tmp = tmp.next;}return tmp;}
解法②：双指针（快慢指针）定位
要找到倒数第K个节点的Node，可以同时开启两个指针，一开始分别记录第一个节点和正数第K个节点的位置，然后让指针往后挪动，当第二个指针指向链表的末尾Node时，第一个指针正好指向倒数第K个节点。（相当于慢的指针没走的K步由快指针走完）
public static void main(String[] args) {int[] arr = {1,2,3,4,5,6};ListNode head = ListNode.arrayToListNode(arr);ListNode kthFromEnd = getKthFromEnd1(head, 3);System.out.println(kthFromEnd.val);}public static ListNode getKthFromEnd1(ListNode head,int k){ListNode fast = head;ListNode slow = head;for (int i = 0; i < k - 1; i++) {fast=fast.next;}while (null != fast.next){fast = fast.next;slow = slow.next;System.out.println("slow走到了"+slow.val+"处，fast走到了"+fast.val+"处。");}return slow;}
【过程示例】
slow走到了2处，fast走到了4处。
slow走到了3处，fast走到了5处。
slow走到了4处，fast走到了6处。
4
二、反转链表
【描述】让一个节点的next指向前置节点，让原next节点指向自身。也就是记录前置节点，变更指向。注意在引用更改时，会丢失原next节点的引用，需要用临时的指针temp记录一下
解法：声明临时节点依次挪动
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
ListNode head = ListNode.arrayToListNode(arr);
ListNode head1 = reverseList(head);
ListNode.print(head1);
}
public static ListNode reverseList(ListNode head){
//pre初始化为null;
ListNode pre = null;
//从head开始移动
ListNode cur = head;
while (cur != null){
//拿出cur当前移动至的节点它的下一个节点
ListNode tmp = cur.next;
//将移动至的当前节点的next指针指向pre
cur.next = pre;
//pre更新，变为当前节点cur
pre = cur;
//cur更新，变为原cur的next节点。完成挪动
cur = tmp;
}
//cur最终会挪到最后一个节点的next节点，所以要返回pre作为新链表的head节点
return pre;
}
三、判断一个链表是否是环形链表
解法①：使用快慢指针
跑步时，操场是一个环形跑道，跑的快的人和跑的慢的人终将相遇，这就能倒推出跑道是环形的。
构造一个快指针，让其一次遍历两个节点，一个慢指针一次遍历一个节点
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8};
ListNode listNode = ListNode.arrayToListNode(arr);
ListNode.toCycle(listNode,3);
boolean b = hasCycle(listNode);
System.out.println(b);
}
public static boolean hasCycle(ListNode head){
if (null == head || null == head.next){
return false;
}
ListNode slow = head;
ListNode fast = head;
while (true){
slow = slow.next;
fast = fast.next.next;
if (null == fast || null == fast.next){
return false;
}
if (slow == fast){
return true;
}
if (null != slow){
System.out.print("slow走到了"+slow.val+"位置，");
}
if (null != fast){
System.out.println("fast走到了"+fast.val+"位置。");
}
}
}
控制台打印输出
slow走到了2位置，fast走到了3位置。
slow走到了3位置，fast走到了5位置。
slow走到了4位置，fast走到了7位置。
slow走到了5位置，fast走到了4位置。
true
123456 78
2 3 4 5 6 7 8 7 8 7 8
3 5 7 7 7
四、判断一个链表是否是环形链表，如是返回其入口节点，不是返回空
解法①：快慢指针相遇
第一次相遇之后，让fast重新指向头节点head，slow保持不变。fast和slow按照相同速度移动，第二次相遇后，此节点即为入口节点。
public static ListNode detectCycle(ListNode head){
if (null == head || null == head.next){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (true){
slow = slow.next;
fast = fast.next.next;
if (null == fast || null == fast.next){
return null;
}
if (slow == fast){
break;
}
if (null != slow){
System.out.print("slow走到了"+slow.val+"位置，");
}
if (null != fast){
System.out.println("fast走到了"+fast.val+"位置。");
}
}
fast = head;
while (true){
fast = fast.next;
slow = slow.next;
if (fast == slow){
return slow;
}
}
}
五、经典链表应用之“约瑟夫环”
【描述】假设有N个人围成一圈，从第一个人开始报数，报到第M个人时，第M个人被杀，然后下一个人继续从1开始报数，报至第M个人时第M个人也被杀，依次循环直至最后一个。那么最后一个人的初始位置在哪里？
解法①：链表方式
【分析】将每个人视作链表中的一个节点，当遍历至M的时候删除该节点，然后从M处开始重新遍历，直至剩下最后一个节点。
public static void main(String[] args) {
System.out.println("41,3 ->"+josephus(41,3));
}
public static int josephus(int n,int m){
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i+1;
}
ListNode head = ListNode.arrayToListNode(arr);
ListNode.toCycle(head,0);
int cnt = 1;
while (true){
//在m位置处的节点要被删去，那就需要将m-1位置处的节点next指向next.next
if (cnt == m-1){
System.out.println("在第"+head.next.val+"处的值被删除");
head.next=head.next.next;
//m位置处的节点被删去后，将cnt置为0重新计数
//之所以不置为1，因为下面回有cnt++抵消
cnt = 0;
}
//指针向后移动一位起到遍历作用
head = head.next;
cnt++;
//当某一个节点的next节点指向自己的时候，说明只剩下一个节点了，那该节点的值即为结果
if (head == head.next){
return head.val;
}
}
}
解法②：数组方式
【分析】将每个人视作数组中的一个元素，当报数到m的时候，使用占位符代表此人死掉了。再次遍历时跳过该占位符标记的位置。当剩余人数只有一人时，即为结果。
public static int josephus1(int n,int m){
int[] people = new int[n];
int index = -1;
int cnt = 0;
int remain = n;
while (remain >= 1){
index++;
if (index >= n){
index = 0;
}
if (people[index] == -1){continue;}
System.out.println("cnt 等于:"+cnt+",index为"+index);
if (cnt == m){
people[index] = -1;
System.out.println("cnt 等于:"+cnt+"第"+index+"位置处的元素被删除");
remain--;
cnt = 0;
}
cnt++;
}
return index;
}
若有收获，就点个赞吧
0 人点赞
