java的單鏈表環(huán)操作有哪些

判斷鏈表中是否有環(huán)

先來看一張圖：

 

我們能夠清楚的看到，在這個(gè)單鏈表中，是有環(huán)的。那么使用代碼，該如何判斷它是否有環(huán)呢？

先別著急看代碼，先和阿粉一起來分析一下，有了思路，代碼實(shí)現(xiàn)相對就比較容易。

判斷鏈表中是否有環(huán)，可以從頭結(jié)點(diǎn)開始，依次遍歷單鏈表中的每一個(gè)節(jié)點(diǎn)。每遍歷一個(gè)節(jié)點(diǎn)，就和前面的所有節(jié)點(diǎn)作比較，如果發(fā)現(xiàn)新節(jié)點(diǎn)和之前的某個(gè)節(jié)點(diǎn)相同，則說明此節(jié)點(diǎn)被遍歷過兩次，說明鏈表有環(huán)，反之就是沒有。

但是仔細(xì)看一下這種方法，你會(huì)發(fā)現(xiàn)這種方法很耗時(shí)耗力，因?yàn)槊勘闅v一個(gè)節(jié)點(diǎn)，都要把它和前面所有的節(jié)點(diǎn)都比較一遍。別著急，阿粉還有一個(gè)很巧妙的方法，就是使用兩個(gè)指針。這樣思路就可以這樣想：

使用兩個(gè)指針，一個(gè)快指針，一個(gè)慢指針?？熘羔樏看巫?2 步，慢指針每次走 1 步。如果鏈表中沒有環(huán)，則快指針會(huì)先指向 null 如果鏈表中有環(huán)，則快慢指針一定會(huì)相遇。

思路打通，咱們就可以使用代碼來進(jìn)行實(shí)現(xiàn)了：

/**
* 判斷鏈表是否有環(huán)
*/
public class IsHasLoop {
   public static class Node{
       private int data;
       private Node next;
       public Node(int data,Node next){
           this.data=data;
           this.next=next;
       }
       public int getData(){
           return data;
       }
   }
   public static void main(String[] args){
       // 初始化單鏈表
       Node node5=new Node(5,null);
       Node node4=new Node(4,node5);
       Node node3=new Node(3,node4);
       Node node2=new Node(2,node3);
       Node node1=new Node(1,node2);
       // 讓 node5 的指針指向 node1 形成一個(gè)環(huán)
       node5.next=node1;

       boolean flag=isHasLoop(node1);
       System.out.println(flag);

   }
   public static boolean isHasLoop(Node list){
       if (list == null){
           return false;
       }

       Node slow=list;
       Node fast=list;

       while (fast.next != null && fast.next.next != null){
           // 慢指針走一步,快指針走兩步
           slow=slow.next;
           fast=fast.next.next;
           // 如果快慢指針相遇,則說明鏈表中有環(huán)
           if (slow==fast){
               return true;
           }
       }
// 反之鏈表中沒有環(huán)
       return false;
   }
}

求環(huán)長

現(xiàn)在判斷鏈表中是否有環(huán)這個(gè)問題已經(jīng)解決了，阿粉覺得不能到此為止，思路就向外擴(kuò)散了一下，既然有環(huán)了，如果想要求環(huán)長該怎么辦呢？

既然快慢指針相遇了，阿粉記錄下此時(shí)的位置，接下來再讓滿指針繼續(xù)向前走，每次走 1 步，這樣當(dāng)慢指針再次走到相遇時(shí)的位置時(shí)，慢指針走過的長度不就是環(huán)長嘛

public static int getLength(Node list){
       // 定義環(huán)長初始值為 0
       int loopLength=0;
       Node slow=list;
       Node fast=list;

       while (fast != null && fast.next != null) {
           // 慢指針走一步,快指針走兩步
           slow=slow.next;
           fast=fast.next.next;

           // 第一次相遇時(shí)跳出循環(huán)
           if (slow == fast) break;
       }
       // 如果 fast next 指針首先指向 null 指針,說明該鏈表沒有環(huán),則環(huán)長為 0
       if(fast.next == null || fast.next.next == null){
           return 0;
       }
       // 如果有環(huán),使用臨時(shí)變量保存當(dāng)前的鏈表
       Node temp = slow;
       // 讓慢指針一直走,直到走到原來位置
       do{
           slow = slow.next;
           loopLength++;
       } while(slow != temp);

       return loopLength;
}

求入環(huán)點(diǎn)

既然有環(huán)了，也求出了環(huán)長，那么入環(huán)點(diǎn)應(yīng)該也知道了吧？阿粉對于求入環(huán)點(diǎn)這個(gè)問題有點(diǎn)兒懵，就畫了一張圖出來：

 

如上圖，我們假設(shè)：

入環(huán)點(diǎn)距離頭結(jié)點(diǎn)距離為 D 入環(huán)點(diǎn)與首次相遇點(diǎn)較短的距離為 S1 入環(huán)點(diǎn)與首次相遇點(diǎn)較長的距離為 S2 當(dāng)兩個(gè)指針首次相遇時(shí)，慢指針一次只走 1 步，則它所走的距離為：D+S1 快指針每次走 2 步，多走了 n(n>=1) 圈，則它所走的距離為：D+S1+n(S1+S2) 快指針?biāo)俣葹槁羔樀?2 倍，則：2(D+S1)=D+S1+n(S1+S2) 上面等式，整理可得：D=(n-1)(S1+S2)+S2

如果讓 (n-1)(S1+S2) 為 0 ，是不是 D 和 S2 就相等了？也就是說，當(dāng)兩個(gè)指針第一次相遇時(shí)，只要把其中一個(gè)指針放回到頭結(jié)點(diǎn)位置，另外一個(gè)指針保持在首次相遇點(diǎn)，接下來兩個(gè)指針每次都向前走 1 步，接下來這兩個(gè)指針相遇時(shí)，就是要求的入環(huán)點(diǎn)。

有點(diǎn)兒像做數(shù)學(xué)題的感覺，還好阿粉的數(shù)學(xué)功底還是有那么一丟丟的。

基于上面的思路，代碼就很容易實(shí)現(xiàn)了：

public static Node entryNodeOfLoop(Node list){
       Node slow=list;
       Node fast=list;
       while(fast.next != null && fast.next.next != null){
           // 慢指針走一步,快指針走兩步
           slow=slow.next;
           fast=fast.next.next;

           // 第一次相遇時(shí)跳出循環(huán)
           if (slow == fast) break;
       }
       // 如果 fast next 指針首先指向 null 指針,說明該鏈表沒有環(huán),則入環(huán)點(diǎn)為 null
       if (fast.next == null || fast.next.next == null){
           return  null;
       }
       // 第一次相遇之后,讓一個(gè)指針指向頭結(jié)點(diǎn),另外一個(gè)指針在相遇位置
       // 兩個(gè)指針每次走 1 步,相遇為止,此時(shí)相遇節(jié)點(diǎn)即為入環(huán)點(diǎn)
       Node head=list; // 頭結(jié)點(diǎn)
       Node entryNode=slow;    // 相遇節(jié)點(diǎn)
       while (entryNode != head){
           entryNode=entryNode.next;
           head=head.next;
       }
       return entryNode;
}