1.怎么找到鏈表的中心元素？
咱們能夠選用快慢指針的思維，運用步長為1的慢指針和步長為2的快指針，當快指針抵達鏈表結(jié)尾時，此時慢指針指向的即為中點方位。
publicstaticLinkNodefindMiddleByPointer(LinkNodenode){
LinkNodeslow=node;
LinkNodefast=node;//檢測快指針是否能夠安全移動while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}returnslow;
}
咱們還能夠選用遞歸的方式，當遞歸到最結(jié)尾的時分，咱們現(xiàn)已能知道鏈表的長度，此時當遞歸回去的時分，判別當時遞歸層級等于鏈表長度一半的時分，即為鏈表的要點。
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.檢測鏈表是否有環(huán)。
檢測鏈表是否有環(huán)是非常常見的算法考察。常見的就是運用快慢指針，假如快慢指針有重合的時分，說明鏈表是有環(huán)的。
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.怎么列表回轉(zhuǎn)（遞歸）
咱們能夠在遞歸回溯的時分，反向更改節(jié)點的指針。
publicstaticvoidreverseLinkListByRecursion(LinkNodecur,LinkNodenext){if(next==null){
return;
}
reverseLinkListByRecursion(next,next.next);next.next=cur;
cur.next=null;
return;
}
4.怎么回轉(zhuǎn)鏈表（非遞歸）
回轉(zhuǎn)鏈表的非遞歸方式，咱們能夠選用三個指針，別離指向當時節(jié)點，下個節(jié)點，下下個節(jié)點，調(diào)整好下個節(jié)點的next指向后，持續(xù)使用下下個節(jié)點進行往后操作。
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.刪去經(jīng)過排序的鏈表中重復的節(jié)點。
通過在遍歷中，判別當時的數(shù)字是否與之前的重復數(shù)字相同，假如相同的話，直接越過，直到找到與之前重復數(shù)字不同時，將原先的指針越過重復的節(jié)點，指向當時非重復數(shù)字節(jié)點。
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.怎么核算兩個鏈表的代表數(shù)字之和。
將鏈表代表的數(shù)字進行相加即可，注意首位代表的是個位。3->1->5代表513，5->9->2代表295，最終核算結(jié)果為8->0->8，808。
publicstaticLinkNodesumTwoLinkList(LinkNodenum1,LinkNodenum2){//假如其間一個鏈表為空的，直接當做0處理，回來另外一個鏈表if(num1==null){returnnum2;
}if(num2==null){returnnum1;
}
LinkNodesum=newLinkNode();//保存頭結(jié)點，假如核算完成后直接回來頭結(jié)點LinkNodehead=sum;//是否進位booleanisOver=false;//當兩個節(jié)點，其間一個存在時，即可進行累加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;//沒有數(shù)字相加，直接結(jié)束if(num1==null&&num2==null){break;
}else{//還有數(shù)字相加的話提前生成下個數(shù)字sum.next=newLinkNode();
sum=sum.next;
}
}returnhead;
}
7.鏈表-奇數(shù)位升序偶數(shù)位降序-讓鏈表變成升序
先將鏈表拆分紅奇數(shù)的鏈表，和偶數(shù)的鏈表，然后翻轉(zhuǎn)偶數(shù)的鏈表，在兼并兩個鏈表。
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);//先按奇數(shù)偶數(shù)位拆分鏈表splitList(x1);//再回轉(zhuǎn)鏈表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;
}
}
}/**
*回轉(zhuǎn)鏈表
*@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.一個單向鏈表，刪去倒數(shù)第N個數(shù)據(jù)。
預備兩個指針，初始指向頭結(jié)點，1號指針先走n步，然后2號指針開始走，當1號指針走到尾節(jié)點時，2號指針即為倒數(shù)第N個數(shù)據(jù)。
publicstaticLinkNodefindLastKNumber(LinkNodenode,intk){
LinkNodefast=node;
LinkNodeslow=node;for(inti=0;i<k;i++){//假如fast為空的話，說明k超出規(guī)模if(fast==null){thrownewRuntimeException(“超出鏈表規(guī)模！”);
}
fast=fast.next;
}while(fast!=null){
fast=fast.next;
slow=slow.next;
}returnslow;
}
筆者個人總結(jié)，如有過錯之處望不吝指出。