（4）链表的复杂度分析
get(int i):每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间 复杂度为 O(n)
insert(int i,T t):每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的 元素越多，时间复杂度为 O(n);
remove(int i):每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元 素越多，时间复杂度为 O(n)
相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的， 它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。
相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删 操作比较多，建议使用链表。
（5）链表反转
单链表的反转，是面试中的一个高频题目。
需求：
原链表中数据为：1->2->3>4
反转后链表中数据为：4->3->2->1
反转API：
public void reverse()：对整个链表反转
public Node reverse(Node curr)：反转链表中的某个结点curr,并把反转后的curr结点返回
使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点， 直到把最后一个结点反转完毕，整个链表就反转完毕。
代码：
/** * 链表反转 * 反转整个链表 * @return */ public void reverse(){ // 判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转 if (isEmpty()){ return; } reverse(head.next); } /** * 反转指定的节点curr，并把反转后的节点返回 * @return */ public Node<T> reverse(Node<T> curr){ if (curr.next == null){ head.next = curr; return curr; } // 递归的反转当前节点curr的下一个节点；返回值就是链表反转后当前节点的上一个节点 Node<T> pre = reverse(curr.next); // 让返回的节点的下一个节点变为当前节点curr pre.next = curr; // 把当前节点的下一个节点变为null curr.next = null; return curr; }
测试代码：
package cn.itcast.algorithm.test; import cn.itcast.algorithm.linear.LinkList; /** * @author ：caizhengjie * @description：TODO * @date ：2021/2/2 12:11 上午 */ public class LinkListTest2 { public static void main(String[] args) { // 创建单向链表对象 LinkList<String> l1 = new LinkList<>(); // 测试插入 l1.insert("alex"); l1.insert("lili"); l1.insert("jone"); l1.insert(1,"jack"); // 遍历 for (String s : l1) { System.out.println(s); } System.out.println("---------------------------------------"); // 反转链表 l1.reverse(); for (String s : l1) { System.out.println(s); } } }
运行结果：
alex jack lili jone --------------------------------------- jone lili jack alex
（6）快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以然 我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍
（6.1）中间值问题
利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以 此来达到找到中间节点的目的。 如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。
代码：
package cn.itcast.algorithm.test; public class FastSlowTest { public static void main(String[] args) throws Exception { //创建结点 Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; //查找中间值 String mid = getMid(first); System.out.println("中间值为："+mid); } /** * @param first 链表的首结点 * @return 链表的中间结点的值 */ public static String getMid(Node<String> first) { //定义两个指针 Node<String> fast = first; Node<String> slow = first; //使用两个指针遍历链表，当快指针指向的结点没有下一个结点了，就可以结束了，结束之后，慢指针指向的结点就是中间值 while(fast!=null && fast.next!=null){ //变化fast的值和slow的值 fast = fast.next.next; slow=slow.next; } return slow.item; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
运行结果：
中间值为：dd
（6.2）单向链表是否有环问题
使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道 中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。
测试代码：
package cn.itcast.algorithm.test; public class CircleListCheckTest { public static void main(String[] args) throws Exception { //创建结点 Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; // 产生环 seven.next = third; //判断链表是否有环 boolean circle = isCircle(first); System.out.println("first链表中是否有环："+circle); } /** * 判断链表中是否有环 * @param first 链表首结点 * @return ture为有环，false为无环 */ public static boolean isCircle(Node<String> first) { // 定义快慢指针 Node<String> fast = first; Node<String> slow = first; // 遍历链表，如果快慢指针指向同一个节点，那么证明有环 while (fast != null && fast.next != null){ // 变换fast和slow fast = fast.next.next; slow = slow.next; if (fast.equals(slow)){ return true; } } return false; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
运行结果：
first链表中是否有环：true
（6.3）有环链表入口问题
当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样 为1，则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识，这里略，只讲实现。
测试代码：
package cn.itcast.algorithm.test; public class CircleListInTest { public static void main(String[] args) throws Exception { Node<String> first = new Node<String>("aa", null); Node<String> second = new Node<String>("bb", null); Node<String> third = new Node<String>("cc", null); Node<String> fourth = new Node<String>("dd", null); Node<String> fifth = new Node<String>("ee", null); Node<String> six = new Node<String>("ff", null); Node<String> seven = new Node<String>("gg", null); //完成结点之间的指向 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; fifth.next = six; six.next = seven; //产生环 seven.next = third; //查找环的入口结点 Node<String> entrance = getEntrance(first); System.out.println("first链表中环的入口结点元素为："+entrance.item); } /** * 查找有环链表中环的入口结点 * @param first 链表首结点 * @return 环的入口结点 */ public static Node getEntrance(Node<String> first) { //定义快慢指针 Node<String> fast = first; Node<String> slow = first; Node<String> temp = null; // 遍历链表，先找到环（快慢指针相遇），准备一个临时指针，指向链表的首节点， // 继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的节点就是环的入口 while (fast != null && fast.next != null){ // 变换fast和slow fast = fast.next.next; slow = slow.next; // 判断快慢指针是否相遇 if (fast.equals(slow)){ temp = first; continue; } // 让临时节点变换 if (temp != null){ temp = temp.next; // 判断临时指针是否和临时指针相遇 if (temp.equals(slow)){ break; } } } // 返回环的入口 return temp; } //结点类 private static class Node<T> { //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } }
运行结果：
first链表中环的入口结点元素为：cc
（7）循环链表
循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结 点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。
（8）约瑟夫问题
问题描述：
传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决 定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往 后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡 为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与 第31个位置，从而逃过了这场死亡游戏 。
问题转换：
41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
自退出那个人开始的下一个人再次从1开始报数，以此类推；
求出最后退出的那个人的编号。
图示：
解题思路：
构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
使用计数器count，记录当前报数的值；
遍历链表，每循环一次，count++；
判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
测试代码：
package cn.itcast.algorithm.test; /** * @author ：caizhengjie * @description：TODO * @date ：2021/8/4 11:56 下午 * 约瑟夫问题 */ public class JosepTest { /** * 节点类实现 */ public static class Node<T>{ // 存储元素 public T item; // 指向下一个节点 public Node<T> next; public Node(T item, Node<T> next){ this.item = item; this.next = next; } } public static void main(String[] args) { // 1.构建循环链表，包含41个节点，分别存储1-41之间的值 // first用来记录首节点 Node<Integer> first = null; // pre用来记录前一个节点 Node<Integer> pre = null; for (int i = 1; i <= 41; i++){ // 如果是第一个节点 if (i == 1){ first = new Node<>(i,null); pre = first; continue; } // 如果不是第一个节点 Node<Integer> newNode = new Node<>(i,null); pre.next = newNode; pre = newNode; // 如果是最后一个节点，那么需要让最后一个节点的下一个节点变为first，变成循环链表 if(i == 41){ pre.next = first; } } // 2.需要count计数器，模拟报数 int count = 0; // 3.遍历循环链表 // 记录每次遍历拿到的节点，默认从首节点开始 Node<Integer> n = first; // 记录当前节点的上一个节点 Node<Integer> before = null; while (n != n.next){ // 模拟报数 count++; // 判断当前报数是不是3 if (count == 3){ // 如果是3，则把当前节点删除调用，打印当前节点，重置count=0，让当前节点n后移 before.next = n.next; System.out.println(n.item + ","); count = 0; n = n.next; } else { // 如果不是3，让before变成当前节点，让当前节点后移 before = n; n = n.next; } } // 打印出最后一个元素 System.out.println(n.item); } }
