链表–常见应用场景链表反转单向表的反转是面试中的一个高频题目。需求单向链表原链表中数据为1-2-34反转后链表中数据为4-3-2-1反转API原来解析:使用递归可以完成反转递归反转其实就是从原链表的第一个存数据的结点开始依次递归调用反转每一个结点直到把最后一个结点反转完毕整个链表就反转完毕。代码实现:单向链表LinkList//用来反转整个链表publicvoidreverse(){//判断当前链表是否为空链表如果是空链表则结束运行如果不是则调用重载的reverse方法完成反转if(isEmpty()){return;}reverse(head.next);}//反转指定的结点curr并把反转后的结点返回publicNodereverse(Nodecurr){if(curr.nextnull){head.nextcurr;returncurr;}//递归的反转当前结点curr的下一个结点返回值就是链表反转后当前结点的上一个结点Nodeprereverse(curr.next);//让返回的结点的下一个结点变为当前结点currpre.nextcurr;//把当前结点的下一个结点变为nullcurr.nextnull;returncurr;}测试:Testpublicvoidtest01(){LinkListIntegerlistnewLinkList();list.insert(1);list.insert(2);list.insert(3);list.insert(4);for(Integeri:list){System.out.print(i );}System.out.println();System.out.println(--------------------);list.reverse();for(Integeri:list){System.out.print(i );}}快慢指针快慢指针指的是定义两个指针这两个指针的移动速度一块一慢以此来制造出自己想要的差值这个差值可以然我们找到链表上相应的结点。一般情况下快指针的移动步长为慢指针的两倍1. 中间值问题需求;找到一串节点当中的中间值元素原理分析:利用快慢指针我们把一个链表看成一个跑道假设a的速度是b的两倍那么当a跑完全程后b刚好跑一半以此来达到找到中间节点的目的。图解:如下图最开始slow与fast指针都指向链表第一个节点然后slow每次移动一个指针fast每次移动两个指针。代码/** * param first 链表的首结点 * return 链表的中间结点的值 */publicstaticStringgetMid(NodeStringfirst){//定义两个指针NodeStringfastfirst;NodeStringslowfirst;//使用两个指针遍历链表当快指针指向的结点没有下一个结点了就可以结束了结束之后慢指针指向的结点就是中间值while(fast!nullfast.next!null){//变化fast的值和slow的值fastfast.next.next;slowslow.next;}returnslow.item;}测试:publicclassFastSlowTest{publicstaticvoidmain(String[]args)throwsException{//创建结点NodeStringfirstnewNodeString(aa,null);NodeStringsecondnewNodeString(bb,null);NodeStringthirdnewNodeString(cc,null);NodeStringfourthnewNodeString(dd,null);NodeStringfifthnewNodeString(ee,null);NodeStringsixnewNodeString(ff,null);NodeStringsevennewNodeString(gg,null);//完成结点之间的指向first.nextsecond;second.nextthird;third.nextfourth;fourth.nextfifth;fifth.nextsix;six.nextseven;//查找中间值StringmidgetMid(first);System.out.println(中间值为mid);}/** * param first 链表的首结点 * return 链表的中间结点的值 */publicstaticStringgetMid(NodeStringfirst){//定义两个指针NodeStringfastfirst;NodeStringslowfirst;//使用两个指针遍历链表当快指针指向的结点没有下一个结点了就可以结束了结束之后慢指针指向的结点就是中间值while(fast!nullfast.next!null){//变化fast的值和slow的值fastfast.next.next;slowslow.next;}returnslow.item;}//结点类privatestaticclassNodeT{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}}2. 单向链表是否有环问题原理解析:使用快慢指针的思想还是把链表比作一条跑道链表中有环那么这条跑道就是一条圆环跑道在一条圆环跑道中两个人有速度差那么迟早两个人会相遇只要相遇那么就说明有环。代码/** * 判断链表中是否有环 * param first 链表首结点 * return ture为有环false为无环 */publicstaticbooleanisCircle(NodeStringfirst){//定义快慢指针NodeStringfastfirst;NodeStringslowfirst;//遍历链表如果快慢指针指向了同一个结点那么证明有环while(fast!nullfast.next!null){//变换fast和slowfastfast.next.next;slowslow.next;if(fast.equals(slow)){returntrue;}}returnfalse;}测试publicclassCircleListCheckTest{publicstaticvoidmain(String[]args)throwsException{//创建结点NodeStringfirstnewNodeString(aa,null);NodeStringsecondnewNodeString(bb,null);NodeStringthirdnewNodeString(cc,null);NodeStringfourthnewNodeString(dd,null);NodeStringfifthnewNodeString(ee,null);NodeStringsixnewNodeString(ff,null);NodeStringsevennewNodeString(gg,null);//完成结点之间的指向first.nextsecond;second.nextthird;third.nextfourth;fourth.nextfifth;fifth.nextsix;six.nextseven;// //产生环seven.nextthird;//判断链表是否有环booleancircleisCircle(first);System.out.println(first链表中是否有环circle);}/** * 判断链表中是否有环 * param first 链表首结点 * return ture为有环false为无环 */publicstaticbooleanisCircle(NodeStringfirst){//定义快慢指针NodeStringfastfirst;NodeStringslowfirst;//遍历链表如果快慢指针指向了同一个结点那么证明有环while(fast!nullfast.next!null){//变换fast和slowfastfast.next.next;slowslow.next;if(fast.equals(slow)){returntrue;}}returnfalse;}//结点类privatestaticclassNodeT{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}}3. 有环链表入口问题:原理解析:当快慢指针相遇时我们可以判断到链表中有环这时重新设定一个新指针指向链表的起点且步长与慢指针一样为1则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识这里略只讲实现。代码:/** * 查找有环链表中环的入口结点 * param first 链表首结点 * return 环的入口结点 */publicstaticNodegetEntrance(NodeStringfirst){//定义快慢指针NodeStringfastfirst;NodeStringslowfirst;NodeStringtempnull;//遍历链表先找到环(快慢指针相遇),准备一个临时指针指向链表的首结点继续遍历直到慢指针和临时指针相遇那么相遇时所指向的结点就是环的入口while(fast!nullfast.next!null){//变换快慢指针fastfast.next.next;slowslow.next;//判断快慢指针是否相遇if(fast.equals(slow)){tempfirst;continue;}//让临时结点变换if(temp!null){temptemp.next;//判断临时指针是否和慢指针相遇if(temp.equals(slow)){break;}}}returntemp;测试:packagemain.java.Algorithms.linear;publicclassCircleListInTest{publicstaticvoidmain(String[]args)throwsException{NodeStringfirstnewNodeString(aa,null);NodeStringsecondnewNodeString(bb,null);NodeStringthirdnewNodeString(cc,null);NodeStringfourthnewNodeString(dd,null);NodeStringfifthnewNodeString(ee,null);NodeStringsixnewNodeString(ff,null);NodeStringsevennewNodeString(gg,null);//完成结点之间的指向first.nextsecond;second.nextthird;third.nextfourth;fourth.nextfifth;fifth.nextsix;six.nextseven;//产生环seven.nextthird;//查找环的入口结点NodeStringentrancegetEntrance(first);System.out.println(first链表中环的入口结点元素为entrance.item);}/** * 查找有环链表中环的入口结点 * param first 链表首结点 * return 环的入口结点 */publicstaticNodegetEntrance(NodeStringfirst){//定义快慢指针NodeStringfastfirst;NodeStringslowfirst;NodeStringtempnull;//遍历链表先找到环(快慢指针相遇),准备一个临时指针指向链表的首结点继续遍历直到慢指针和临时指针相遇那么相遇时所指向的结点就是环的入口while(fast!nullfast.next!null){//变换快慢指针fastfast.next.next;slowslow.next;//判断快慢指针是否相遇if(fast.equals(slow)){tempfirst;continue;}//让临时结点变换if(temp!null){temptemp.next;//判断临时指针是否和慢指针相遇if(temp.equals(slow)){break;}}}returntemp;}//结点类privatestaticclassNodeT{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}}约瑟夫问题问题描述问题转换首先41个人坐一圈第一个人编号为1第二个人编号为2第n个人编号为n。编号为1的人开始从1报数依次向后报数为3的那个人退出圈自退出那个人开始的下一个人再次从1开始报数以此类推求出最后退出的那个人的编号。图示解题思路构建含有41个结点的单向循环链表分别存储1~41的值分别代表这41个人使用计数器count记录当前报数的值遍历链表每循环一次count判断count的值如果是3则从链表中删除这个结点并打印结点的值把count重置为0代码:善于创建临时变量指针来记录关键元素packagemain.java.Algorithms.linear;importorg.jetbrains.annotations.NotNull;/** * 解决约瑟夫问题 */publicclassJosephTest01{publicstaticvoidmain(String[]args){//1.构建循环链表包含41个结点分别存储1~41之间的值NodeIntegerfirstgetNodeList();//2.遍历循环链表,找出报数为3的节点,并打印出来run(first);}/** * 构建循环链表包含41个结点分别存储1~41之间的值 * return 返回链表存储的第一个元素 */privatestaticNodeIntegergetNodeList(){//用来就首结点NodeIntegerfirstnull;//用来记录前一个结点NodeIntegerprenull;for(inti1;i41;i){//如果是第一个结点if(i1){firstnewNode(i,null);prefirst;continue;}//如果不是第一个结点NodeIntegernewNodenewNode(i,null);pre.nextnewNode;prenewNode;//如果是最后一个结点那么需要让最后一个结点的下一个结点变为first,变为循环链表了if(i41){pre.nextfirst;}}returnfirst;}/** * 遍历循环链表,找出报数为3的节点,并打印出来 */privatestaticvoidrun(NodeIntegerfirst){//1.需要count计数器模拟报数intcount0;//2.遍历循环链表//记录每次遍历拿到的结点默认从首结点开始NodeIntegernfirst;//记录当前结点的上一个结点NodeIntegerbeforenull;while(n!n.next){//模拟报数count;//判断当前报数是不是为3if(count3){//如果是3则把当前结点删除调用打印当前结点重置count0让当前结点n后移before.nextn.next;System.out.print(n.item,);count0;nn.next;}else{//如果不是3让before变为当前结点让当前结点后移beforen;nn.next;}}//打印最后一个元素System.out.println(n.item);}/** * 结点类 */privatestaticclassNodeT{//存储数据Titem;//下一个结点Nodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}}