常见算法总结 – 链表篇

1.怎么找到链表的中心元素？
咱们能够选用快慢指针的思维，运用步长为1的慢指针和步长为2的快指针，当快指针抵达链表结尾时，此时慢指针指向的即为中点方位。
publicstaticLinkNodefindMiddleByPointer(LinkNodenode){
LinkNodeslow=node;
LinkNodefast=node;//检测快指针是否能够安全移动while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}returnslow;
}
咱们还能够选用递归的方式，当递归到最结尾的时分，咱们现已能知道链表的长度，此时当递归回去的时分，判别当时递归层级等于链表长度一半的时分，即为链表的要点。
publicstaticvoidfindMiddleByRecursion(LinkNodenode,intrecursionIndex){if(node.next!=null){
findMiddleByRecursion(node.next,recursionIndex+1);
}else{
middleIndex=recursionIndex%2==0?recursionIndex/2:recursionIndex/2+1;
}if(middleIndex==recursionIndex){
System.out.println(node.value);
}return;
}
2.检测链表是否有环。
检测链表是否有环是非常常见的算法考察。常见的就是运用快慢指针，假如快慢指针有重合的时分，说明链表是有环的。
publicstaticbooleanisExistCircle(LinkNodenode){
LinkNodeslow=node;
LinkNodefast=node;while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;if(slow==fast){
returntrue;
}
}
returnfalse;
}
3.怎么列表回转（递归）
咱们能够在递归回溯的时分，反向更改节点的指针。
publicstaticvoidreverseLinkListByRecursion(LinkNodecur,LinkNodenext){if(next==null){
return;
}
reverseLinkListByRecursion(next,next.next);next.next=cur;
cur.next=null;
return;
}
4.怎么回转链表（非递归）
回转链表的非递归方式，咱们能够选用三个指针，别离指向当时节点，下个节点，下下个节点，调整好下个节点的next指向后，持续使用下下个节点进行往后操作。
publicstaticvoidreverseLinkListByPointer(LinkNodenode){
LinkNodecur=node;
LinkNodenext=node.next;
LinkNodenextNext=null;
cur.next=null;while(next!=null){
nextNext=next.next;next.next=cur;
cur=next;next=nextNext;
}
}
5.删去经过排序的链表中重复的节点。
通过在遍历中，判别当时的数字是否与之前的重复数字相同，假如相同的话，直接越过，直到找到与之前重复数字不同时，将原先的指针越过重复的节点，指向当时非重复数字节点。
publicstaticvoidremoveDuplicateNode(LinkNodenode){if(node==null){
return;
}
LinkNodecur=node;
LinkNodenext=node.next;intdupicateVal=node.value;while(next!=null){if(next.value==dupicateVal){next=next.next;
continue;
}
dupicateVal=next.value;
cur.next=next;
cur=next;next=next.next;
}
}
6.怎么核算两个链表的代表数字之和。
将链表代表的数字进行相加即可，注意首位代表的是个位。3->1->5代表513，5->9->2代表295，最终核算结果为8->0->8，808。
publicstaticLinkNodesumTwoLinkList(LinkNodenum1,LinkNodenum2){//假如其间一个链表为空的，直接当做0处理，回来另外一个链表if(num1==null){returnnum2;
}if(num2==null){returnnum1;
}
LinkNodesum=newLinkNode();//保存头结点，假如核算完成后直接回来头结点LinkNodehead=sum;//是否进位booleanisOver=false;//当两个节点，其间一个存在时，即可进行累加while(num1!=null||num2!=null){//默认初始化为0intnum1Val=0;intnum2Val=0;if(num1!=null){
num1Val=num1.value;
}if(num2!=null){
num2Val=num2.value;
}//假如进位的话多加1intsingleSum=num1Val+num2Val+(isOver==true?1:0);if(singleSum>=10){
isOver=true;
singleSum=singleSum%10;
}else{
isOver=false;
}
sum.value=singleSum;//移动指针num1=num1!=null?num1.next:null;
num2=num2!=null?num2.next:null;//没有数字相加，直接结束if(num1==null&&num2==null){break;
}else{//还有数字相加的话提前生成下个数字sum.next=newLinkNode();
sum=sum.next;
}
}returnhead;
}
7.链表-奇数位升序偶数位降序-让链表变成升序
先将链表拆分红奇数的链表，和偶数的链表，然后翻转偶数的链表，在兼并两个链表。
publicclassSortAscDescLinkList{publicstaticLinkNodeoddLinkList=null;publicstaticLinkNodeevenLinkList=null;publicstaticvoidmain(String[]args){//初始化测试链表LinkNodex1=newLinkNode(1);
LinkNodex2=newLinkNode(10);
LinkNodex3=newLinkNode(2);
LinkNodex4=newLinkNode(9);
LinkNodex5=newLinkNode(3);
LinkNodex6=newLinkNode(8);
LinkNodex7=newLinkNode(4);
LinkNodex8=newLinkNode(7);
LinkNodex9=newLinkNode(5);
LinkNodex10=newLinkNode(6);
x1.setNext(x2).setNext(x3).setNext(x4).setNext(x5).setNext(x6).setNext(x7).setNext(x8).setNext(x9).setNext(x10);//先按奇数偶数位拆分链表splitList(x1);//再回转链表evenLinkList=reverseLinkList(evenLinkList);//再兼并链表mergeList(oddLinkList,evenLinkList);
oddLinkList.printList();
}/**
*拆分两个链表
*@paramnode
*/publicstaticvoidsplitList(LinkNodenode){
oddLinkList=node;
evenLinkList=node.next;
LinkNodeoddCur=node;
LinkNodeevenCur=node.next;while(oddCur!=null||evenCur!=null){if(oddCur.next!=null&&oddCur.next.next!=null){
oddCur.next=oddCur.next.next;
oddCur=oddCur.next;
}else{
oddCur.next=null;
oddCur=null;
}if(evenCur.next!=null&&evenCur.next.next!=null){
evenCur.next=evenCur.next.next;
evenCur=evenCur.next;
}else{
evenCur.next=null;
evenCur=null;
}
}
}/**
*回转链表
*@paramnode
*@return*/publicstaticLinkNodereverseLinkList(LinkNodenode){
LinkNodecur=node;
LinkNodenext=node.next;
LinkNodenextNext=null;
cur.next=null;while(next!=null){
nextNext=next.next;
next.next=cur;
cur=next;
next=nextNext;
}returncur;
}/**
*兼并两个链表
*@paramoddLinkList
*@paramevenLinkList
*/publicstaticvoidmergeList(LinkNodeoddLinkList,LinkNodeevenLinkList){
LinkNodeoddTail=oddLinkList;while(oddTail.next!=null){
oddTail=oddTail.next;
}
oddTail.next=evenLinkList;
}
}
8.一个单向链表，删去倒数第N个数据。
预备两个指针，初始指向头结点，1号指针先走n步，然后2号指针开始走，当1号指针走到尾节点时，2号指针即为倒数第N个数据。
publicstaticLinkNodefindLastKNumber(LinkNodenode,intk){
LinkNodefast=node;
LinkNodeslow=node;for(inti=0;i<k;i++){//假如fast为空的话，说明k超出规模if(fast==null){thrownewRuntimeException(“超出链表规模！”);
}
fast=fast.next;
}while(fast!=null){
fast=fast.next;
slow=slow.next;
}returnslow;
}
笔者个人总结，如有过错之处望不吝指出。