【Java數據結構】詳解LinkedList與鏈表（二)

1.????前言~🥳🎉🎉🎉

2.反轉一個單鏈表?

3. 找到鏈表的中間節點

4.輸入一個鏈表，輸出該鏈表中倒數第k個結點。?

??5.合并兩個有序鏈表

6.鏈表分割?

7. 判定鏈表的回文結構

8.輸入兩個鏈表，找出它們的第一個公共結點。?

9.?判斷鏈表中是否有環

10.返回鏈表開始入環的第一個節點

?11.總結???????

1.????前言~🥳🎉🎉🎉

Hello, Hello~ 親愛的朋友們👋👋，這里是E綿綿呀????。

如果你喜歡這篇文章，請別吝嗇你的點贊????和收藏📖📖。如果你對我的內容感興趣，記得關注我👀👀以便不錯過每一篇精彩。

當然，如果在閱讀中發現任何問題或疑問，我非常歡迎你在評論區留言指正🗨?🗨?。讓我們共同努力，一起進步！

加油，一起CHIN UP！💪💪

🔗個人主頁：E綿綿的博客
📚所屬專欄：

1.?JAVA知識點專欄

? ? ?? ?深入探索JAVA的核心概念與技術細節

2.JAVA題目練習

? ? ? ??實戰演練，鞏固JAVA編程技能

3.c語言知識點專欄

? ? ? ? 揭示c語言的底層邏輯與高級特性

4.c語言題目練習

? ? ? ? 挑戰自我，提升c語言編程能力

📘 持續更新中，敬請期待?????

這篇文章我們將給大家帶來一些單鏈表的面試題，都很有意思，來看一下吧。

2.反轉一個單鏈表?

? 給你單鏈表的頭節點?head?，請你反轉鏈表，并返回反轉后的鏈表。

我們的解決方法是依次頭插法：

最開始時我們需要將第一個節點的next值變為null，使其變成最后的節點，就產生了新的鏈表。而后依次將原始鏈表中的第二個節點，第三個節點直至最后一個節點頭插到新鏈表中。

這樣就翻轉成功了

完整代碼如下：?
public void reverseList() {if(head==null)return;ListNode cur=head.next;ListNode prev;head.next=null;while(cur!=null){prev=cur.next;cur.next=head;head=cur;cur=prev;}}

這是該題的鏈接：?翻轉鏈表? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

3. 找到鏈表的中間節點

? ?給你單鏈表的頭結點?head?，請你找出并返回鏈表的中間結點。

? ?如果有兩個中間結點，則返回第二個中間結點。

該題的思路實現是設置兩個引用：slow 慢引用和 fast 快引用?

fast 和 slow 同時從head開始遍歷，但是fast一次走兩步，slow一次只走一步，最后我們會發現當 fast遍歷完成后，對應的slow正好是鏈表的中間節點或者第二個中間節點。

fast遍歷完成的標志是fast.next=null或者fast=null

? 完整代碼如下：
public ListNode middleNode(ListNode head) {ListNode fast=head;ListNode  slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;
}

該題鏈接：求鏈表中間結點?

4.輸入一個鏈表，輸出該鏈表中倒數第k個結點。?

該題有兩種思路

?第一種思路：?

第二種思路：

所以我們采用第二種思路去做題，且我們還需要注意k的合法性。

整體代碼如下：

public ListNode FindKthToTail(ListNode head,int k){
if(head==null){
return null;
}
ListNode fast = head;
ListNode slow = head;
//1.判斷k值的合法性
if( k<=0 ){
System.out.println("k值不合法");
return null;
}
//2.讓fast 提前走 k-1 步
while(k-1>0){
if(fast == null |l fast.next ==null){
System.out.println("k值不合法”);
return null;
}
fast = fast.next;
k--;
}
while(fast !=null && fast.next != null){
fast = fast.next;slow = slow.next;
return slow;
}
}

該題題目已下架，無鏈接。

??5.合并兩個有序鏈表

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

?解題思路：

1.先創建一個新的鏈表

2.讓cur1 和 cur2遍歷兩個鏈表，遇到的節點逐個比較，將值小的節點往新鏈表的末尾tail進行尾插

3.上述循環結束后，要判斷有無鏈表還有剩余元素，把剩余的元素尾插到新鏈表的末尾。

? 完整代碼如下：

public  static ListNode mergeTwoLists(ListNode list1, ListNode list2){//將兩個有序鏈表合并為一個有序鏈表ListNode head1=list1;ListNode head2=list2;ListNode head=new ListNode(-1);ListNode cur=head;while(head1!=null&&head2!=null){if(head1.value>head2.value){cur.next=head2;cur=cur.next;head2=head2.next;}else{cur.next=head1;cur=cur.next;head1=head1.next;}}while(head1!=null){cur.next=head1;cur=cur.next;head1=head1.next;}while(head2!=null){cur.next=head2;cur=cur.next;head2=head2.next;}return head.next;}

? 該題鏈接：合并兩個有序鏈表

6.鏈表分割?

現有一鏈表的頭引用?pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

? ?解題思路：

1.創建兩個鏈表，一個鏈表尾插值小于x的節點，另一個鏈表中插值大于等于x的節點

2.遍歷原鏈表，將鏈表中的節點往兩個新鏈表中尾插

3.將兩個鏈表拼接

但是這種思路仍然存在較大的問題，什么問題呢?

1.我們傳入的x值比節點中val都大或者都小，那么存在一個問題就是有一個鏈表中的內容為空，那么按照上面的思路走時，必然會出現空指針異常的情況。

解決方法:??當第一個區間為空時,那么直接返回ca

2.最后一個節點分到小于x的區間，那么最后一個節點的next并不是null，所以此時我們必須手動將 cb.next=null; 預防最后一個節點的next不是null，從而報錯。?

完整代碼如下：

  public static ListNode partition(ListNode pHead, int x) {//給一定值x，該方法將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。if(pHead==null)return  null;ListNode cur=pHead;ListNode  sa=null;ListNode  sb=null;   //小于x的結點所在鏈表ListNode  ca=null;ListNode  cb=null; //大于x的結點所在鏈表while(cur!=null){if(cur.value<x){if(sa==null){sa=cur;sb=cur;cur=cur.next;}else{sb.next=cur;sb=cur;cur=cur.next;}}else{if(ca==null){ca=cur;cb=cur;cur=cur.next;}else{cb.next=cur;cb=cur;cur=cur.next;} }}//拼接兩個鏈表if(sa==null)return  ca;//如果不存在小于X的結點，則直接返回大于x的鏈表，否則按如下執行會報錯if(ca!=null)cb.next=null;//將鏈表中的最后一個結點的next值變為null，防止其循環從而報錯sb.next=ca;return sa;}

題目鏈接：鏈表分割_牛客題霸_牛客網

7. 判定鏈表的回文結構

解題思路實現：

1.找到鏈表的中間節點，找中間節點:采用快慢指針就行了
2.對鏈表的后半部分進行反轉

3.將兩個鏈表從前往后逐個節點進行比對，如果比對之后發現所有節點的值域都相同，則是回文鏈表，否則不是.

并且在循環時還需注意當鏈表為奇數或偶數時，判定循環結束的標志不同：

?奇數是head==slow時結束

?偶數是head.next=slow時結束

所以完整代碼如下：

public static  boolean checkPalindrome(ListNode A) {//判斷鏈表是否為回文結構if(A==null||A.next==null)return true;ListNode slow=A;ListNode fast=A;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}ListNode cur=slow.next;while(cur!=null){ListNode  curnext=cur.next;cur.next=slow;slow=cur;cur=curnext;}ListNode head=A;while(head!=slow){if(head.value!=slow.value)return false;if(head.next==slow)return true;head=head.next;slow=slow.next;}return true;}

注意:在執行完該方法后鏈表結構會被破壞掉，之后如果還對該鏈表進行操作，結果會和我們預想的結果不一樣。

該題鏈接：鏈表的回文結構_牛客題霸_牛客網?

8.輸入兩個鏈表，找出它們的第一個公共結點。?

給你兩個單鏈表的頭節點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回?null?。?

下面是兩個節點相交的各類情況：

從上述鏈表相交的情況看出，兩個單鏈表只要相交，從交點開始，到其后續所有的節點都是兩個鏈表中公共的節點
檢測兩個鏈表是否相交:分別找到兩個鏈表中的最后一個節點，然后檢測這兩個節點的地址是否相同即可：如果地址相同則相交，否則不相交

解題思路：

1.讓較長的鏈表先走兩個鏈表的差值步數

2.再讓兩個鏈表同時往后走，直到遇到地址相同的交點，沒有則返回null

  public static  ListNode getIntersectionNode(ListNode headA, ListNode headB) {//給你兩個單鏈表的頭節點 headA 和 headB ，找出并返回兩個單鏈表相交的起始節點。if(headA==null||headB==null)return null;ListNode cur1=headA;ListNode cur2=headB;int length1=0;int length2=0;while(cur1!=null){length1++;cur1=cur1.next;}while(cur2!=null){length2++;cur2=cur2.next;}cur1=headA;cur2=headB;if(length1>length2){for(int i=0;i<length1-length2;i++){cur1=cur1.next;}}else{for(int i=0;i<length2-length1;i++){cur2=cur2.next;}}while(cur1!=null){if(cur1==cur2)return cur1;cur1=cur1.next;cur2=cur2.next;}return null;}

題目鏈接：找出兩個鏈表的第一個公共節點

9.?判斷鏈表中是否有環

給你一個鏈表的頭節點?head?，判斷鏈表中是否有環。?

解題思路：

設計快慢指針去解決，即慢指針一次走一步，快指針一次走兩步，兩個指針從鏈表起始位置開始運行，如果鏈表帶環則一定會在環中相遇，否則快指針率先走到鏈表的末尾。

擴展問題：

1.為什么快指針每次走兩步，慢指針走一步可以？

假設鏈表帶環，兩個指針最后都會進入環，快指針先進環，慢指針后進環。當慢指針剛進環時，可能就和快指針相遇了，最差情況下兩個指針之間的距離剛好就是環的長度。此時，兩個指針每移動一次，之間的距離就縮小一步，不會出現始終相遇不到的情況，因此：在慢指針走到一圈之前，快指針肯定是可以追上慢指針的，即相遇。

2.快指針一次走3步，走4步，...n步行嗎？

假設:快指針每次走3步，滿指針每次走一步，此時快指針肯定先進環，慢指針后來才進環。假設慢指針進環時候，快指針的位置如圖所示:

此時按照上述方法來繞環移動，每次快指針走3步，慢指針走1步，它們是永遠不會相遇的，因此不行。
只有快指針走2步，慢指針走一步才可以，因為每移動一次，它們之間的距離就縮小一步，無論如何都能相遇。

所以我們在環問題中設置快慢指針，都是將快指針設置為一次兩步，慢指針一次一步，這樣當存在圈時無論如何都會相遇。

? ? 完整代碼如下：

 public static  boolean hasCycle(ListNode head) {//給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。if(head==null||head.next==null)//只有一個節點時默認絕對不存在環return false;ListNode slow=head;ListNode  fast=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast)return true;}return false;}

題目鏈接：判斷鏈表中是否有環

10.返回鏈表開始入環的第一個節點

給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。?

解題思路：

設計一個慢指針，一個快指針，快指針一次兩步，慢指針一次一步。使兩指針相遇而后讓一個指針從鏈表起始位置開始遍歷鏈表，同時也讓一個指針從相遇點的位置開始繞環運行，兩個指針都是每次均走一步，最終肯定會在入口點的位置相遇。??

它們肯定會在入口點相遇的證明如下：

上圖中的H為鏈表的起始點，E為環入口點，M為慢速指針相遇點，設環的長度為R，H到E的距離為L ，E到M的距離為X，則M到E的距離為R-X
在快慢指針相遇過程時，快慢指針相遇時所走的路徑長度:
fast:L +X + nR? ? ? slow:L+ X
注意:

1.當慢指針進入環時，快指針可能已經在環中繞了n圈了，n至少為1。

因為:快指針先進環走到M的位置，最后又在M的位置與慢指針相遇
2.慢指針進環之后，快指針肯定會在慢指針走一圈之內追上慢指針

因為:慢指針進環后，快慢指針之間的距離最多就是環的長度，而兩個指針在移動時，每次它們至今的距離都縮減一步，因此在慢指針移動一圈之前快指針肯定是可以追上慢指針的
而快指針速度是滿指針的兩倍。

所以有如下關系是:

2 *(L+X)=L+X+nR

L+X=nR

L=nR-X(n為1,2,3,4..……，n的大小取決于環的大小，環越小n越大)
極端情況下，假設n=1，此時:L=R-X

所以由此得知一個指針從鏈表起始位置運行，一個指針從相遇點位置繞環，每次都走一步，兩個指針無論如何最終都會在入口點的位置相遇。

? ?完整代碼如下：

public static  ListNode detectCycle(ListNode head) {//給定一個鏈表的頭節點 head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。if(head==null||head.next==null)return null;ListNode slow=head;ListNode  fast=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}return slow;}}return null;}