最新JAVA實(shí)現(xiàn)鏈表面試題
1、單鏈表的創(chuàng)建和遍歷
2、求單鏈表中節(jié)點(diǎn)的個(gè)數(shù)
3、查找單鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)（劍指offer，題15）
4、查找單鏈表中的中間結(jié)點(diǎn)
5、合并兩個(gè)有序的單鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率高】（劍指offer，題17）
6、單鏈表的反轉(zhuǎn)【出現(xiàn)頻率最高】（劍指offer，題16）
7、從尾到頭打印單鏈表（劍指offer，題5）
8、判斷單鏈表是否有環(huán)
9、取出有環(huán)鏈表中，環(huán)的長度
10、單鏈表中，取出環(huán)的起始點(diǎn)（劍指offer，題56）。本題需利用上面的第8題和第9題。
11、判斷兩個(gè)單鏈表相交的第一個(gè)交點(diǎn)（劍指offer，題37）
1、單鏈表的創(chuàng)建和遍歷：
public class LinkList { public Node head; public Node current; //方法：向鏈表中添加數(shù)據(jù) public void add(int data) { //判斷鏈表為空的時(shí)候 if (head == null) {//如果頭結(jié)點(diǎn)為空，說明這個(gè)鏈表還沒有創(chuàng)建，那就把新的結(jié)點(diǎn)賦給頭結(jié)點(diǎn) head = new Node(data); current = head; } else { //創(chuàng)建新的結(jié)點(diǎn)，放在當(dāng)前節(jié)點(diǎn)的后面（把新的結(jié)點(diǎn)合鏈表進(jìn)行關(guān)聯(lián)） current.next = new Node(data); //把鏈表的當(dāng)前索引向后移動一位 current = current.next; //此步操作完成之后，current結(jié)點(diǎn)指向新添加的那個(gè)結(jié)點(diǎn) } } //方法：遍歷鏈表（打印輸出鏈表。方法的參數(shù)表示從節(jié)點(diǎn)node開始進(jìn)行遍歷 public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } class Node { //注：此處的兩個(gè)成員變量權(quán)限不能為private，因?yàn)閜rivate的權(quán)限是僅對本類訪問。 int data; //數(shù)據(jù)域 Node next;//指針域 public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list = new LinkList(); //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 10; i++) { list.add(i); } list.print(list.head);// 從head節(jié)點(diǎn)開始遍歷輸出 } }
上方代碼中，這里面的Node節(jié)點(diǎn)采用的是內(nèi)部類來表示（33行）。使用內(nèi)部類的最大好處是可以和外部類進(jìn)行私有操作的互相訪問。
注：內(nèi)部類訪問的特點(diǎn)是：內(nèi)部類可以直接訪問外部類的成員，包括私有；外部類要訪問內(nèi)部類的成員，必須先創(chuàng)建對象。
為了方便添加和遍歷的操作，在LinkList類中添加一個(gè)成員變量current，用來表示當(dāng)前節(jié)點(diǎn)的索引（03行）。
這里面的遍歷鏈表的方法（20行）中，參數(shù)node表示從node節(jié)點(diǎn)開始遍歷，不一定要從head節(jié)點(diǎn)遍歷。
2、求單鏈表中節(jié)點(diǎn)的個(gè)數(shù)：
注意檢查鏈表是否為空。時(shí)間復(fù)雜度為O（n）。這個(gè)比較簡單。
核心代碼：
//方法：獲取單鏈表的長度 public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length; }
3、查找單鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)：
3.1 普通思路：
先將整個(gè)鏈表從頭到尾遍歷一次，計(jì)算出鏈表的長度size，得到鏈表的長度之后，就好辦了，直接輸出第(size-k)個(gè)節(jié)點(diǎn)就可以了（注意鏈表為空，k為0，k為1，k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)時(shí)的情況
）。時(shí)間復(fù)雜度為O（n），大概思路如下：
public int findLastNode(int index) { //index代表的是倒數(shù)第index的那個(gè)結(jié)點(diǎn) //第一次遍歷，得到鏈表的長度size if (head == null) { return -1; } current = head; while (current != null) { size++; current = current.next; } //第二次遍歷，輸出倒數(shù)第index個(gè)結(jié)點(diǎn)的數(shù)據(jù) current = head; for (int i = 0; i < size - index; i++) { current = current.next; } return current.data; }
如果面試官不允許你遍歷鏈表的長度，該怎么做呢？接下來就是。
3.2 改進(jìn)思路：（這種思路在其他題目中也有應(yīng)用）
這里需要聲明兩個(gè)指針：即兩個(gè)結(jié)點(diǎn)型的變量first和second，首先讓first和second都指向第一個(gè)結(jié)點(diǎn)，然后讓second結(jié)點(diǎn)往后挪k-1個(gè)位置，此時(shí)first和second就間隔了k-1個(gè)位置，然后整體向后移動這兩個(gè)節(jié)點(diǎn)，直到second節(jié)點(diǎn)走到最后一個(gè)結(jié)點(diǎn)的時(shí)候，此時(shí)first節(jié)點(diǎn)所指向的位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)的位置。時(shí)間復(fù)雜度為O（n）
代碼實(shí)現(xiàn)：（初版）
public Node findLastNode(Node head, int index) { if (node == null) { return null; } Node first = head; Node second = head; //讓second結(jié)點(diǎn)往后挪index個(gè)位置 for (int i = 0; i < index; i++) { second = second.next; } //讓first和second結(jié)點(diǎn)整體向后移動，直到second結(jié)點(diǎn)為Null while (second != null) { first = first.next; second = second.next; } //當(dāng)second結(jié)點(diǎn)為空的時(shí)候，此時(shí)first指向的結(jié)點(diǎn)就是我們要找的結(jié)點(diǎn) return first; }
代碼實(shí)現(xiàn)：（最終版）（考慮k大于鏈表中結(jié)點(diǎn)個(gè)數(shù)時(shí)的情況時(shí)，拋出異常）
上面的代碼中，看似已經(jīng)實(shí)現(xiàn)了功能，其實(shí)還不夠健壯:
要注意k等于0的情況；
如果k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)時(shí)，就會報(bào)空指針異常，所以這里需要做一下判斷。
核心代碼如下：
public Node findLastNode(Node head, int k) { if (k == 0 || head == null) { return null; } Node first = head; Node second = head; //讓second結(jié)點(diǎn)往后挪k-1個(gè)位置 for (int i = 0; i < k - 1; i++) { System.out.println("i的值是" + i); second = second.next; if (second == null) { //說明k的值已經(jīng)大于鏈表的長度了 //throw new NullPointerException("鏈表的長度小于" + k); //我們自己拋出異常，給用戶以提示 return null; } } //讓first和second結(jié)點(diǎn)整體向后移動，直到second走到最后一個(gè)結(jié)點(diǎn) while (second.next != null) { first = first.next; second = second.next; } //當(dāng)second結(jié)點(diǎn)走到最后一個(gè)節(jié)點(diǎn)的時(shí)候，此時(shí)first指向的結(jié)點(diǎn)就是我們要找的結(jié)點(diǎn) return first; }
4、查找單鏈表中的中間結(jié)點(diǎn)：
同樣，面試官不允許你算出鏈表的長度，該怎么做呢？
思路：
和上面的第2節(jié)一樣，也是設(shè)置兩個(gè)指針first和second，只不過這里是，兩個(gè)指針同時(shí)向前走，second指針每次走兩步，first指針每次走一步，直到second指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，此時(shí)first指針?biāo)傅慕Y(jié)點(diǎn)就是中間結(jié)點(diǎn)。注意鏈表為空，鏈表結(jié)點(diǎn)個(gè)數(shù)為1和2的情況。時(shí)間復(fù)雜度為O（n）。
代碼實(shí)現(xiàn)：
//方法：查找鏈表的中間結(jié)點(diǎn) public Node findMidNode(Node head) { if (head == null) { return null; } Node first = head; Node second = head; //每次移動時(shí)，讓second結(jié)點(diǎn)移動兩位，first結(jié)點(diǎn)移動一位 while (second != null && second.next != null) { first = first.next; second = second.next.next; } //直到second結(jié)點(diǎn)移動到null時(shí)，此時(shí)first指針指向的位置就是中間結(jié)點(diǎn)的位置 return first; }
上方代碼中，當(dāng)n為偶數(shù)時(shí)，得到的中間結(jié)點(diǎn)是第n/2 + 1個(gè)結(jié)點(diǎn)。比如鏈表有6個(gè)節(jié)點(diǎn)時(shí)，得到的是第4個(gè)節(jié)點(diǎn)。
5、合并兩個(gè)有序的單鏈表，合并之后的鏈表依然有序：
這道題經(jīng)常被各公司考察。
例如：
鏈表1：
1->2->3->4
鏈表2：
2->3->4->5
合并后：
1->2->2->3->3->4->4->5
解題思路：
挨著比較鏈表1和鏈表2。
這個(gè)類似于歸并排序。尤其要注意兩個(gè)鏈表都為空、和其中一個(gè)為空的情況。只需要O (1) 的空間。時(shí)間復(fù)雜度為O (max(len1,len2))
代碼實(shí)現(xiàn)：
//兩個(gè)參數(shù)代表的是兩個(gè)鏈表的頭結(jié)點(diǎn) public Node mergeLinkList(Node head1, Node head2) { if (head1 == null && head2 == null) { //如果兩個(gè)鏈表都為空 return null; } if (head1 == null) { return head2; } if (head2 == null) { return head1; } Node head; //新鏈表的頭結(jié)點(diǎn) Node current; //current結(jié)點(diǎn)指向新鏈表 // 一開始，我們讓current結(jié)點(diǎn)指向head1和head2中較小的數(shù)據(jù)，得到head結(jié)點(diǎn) if (head1.data < head2.data) { head = head1; current = head1; head1 = head1.next; } else { head = head2; current = head2; head2 = head2.next; } while (head1 != null && head2 != null) { if (head1.data < head2.data) { current.next = head1; //新鏈表中，current指針的下一個(gè)結(jié)點(diǎn)對應(yīng)較小的那個(gè)數(shù)據(jù) current = current.next; //current指針下移 head1 = head1.next; } else { current.next = head2; current = current.next; head2 = head2.next; } } //合并剩余的元素 if (head1 != null) { //說明鏈表2遍歷完了，是空的 current.next = head1; } if (head2 != null) { //說明鏈表1遍歷完了，是空的 current.next = head2; } return head; }
代碼測試：
public static void main(String[] args) { LinkList list1 = new LinkList(); LinkList list2 = new LinkList(); //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 4; i++) { list1.add(i); } for (int i = 3; i < 8; i++) { list2.add(i); } LinkList list3 = new LinkList(); list3.head = list3.mergeLinkList(list1.head, list2.head); //將list1和list2合并，存放到list3中 list3.print(list3.head);// 從head節(jié)點(diǎn)開始遍歷輸出 }
上方代碼中用到的add方法和print方法和第1小節(jié)中是一致的。
注：《劍指offer》中是用遞歸解決的，感覺有點(diǎn)難理解。
6、單鏈表的反轉(zhuǎn)：【出現(xiàn)頻率最高】
例如鏈表：
1->2->3->4
反轉(zhuǎn)之后：
4->2->2->1
思路：
從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。時(shí)間復(fù)雜度為O（n）
方法1：（遍歷）
//方法：鏈表的反轉(zhuǎn) public Node reverseList(Node head) { //如果鏈表為空或者只有一個(gè)節(jié)點(diǎn)，無需反轉(zhuǎn)，直接返回原鏈表的頭結(jié)點(diǎn) if (head == null || head.next == null) { return head; } Node current = head; Node next = null; //定義當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) Node reverseHead = null; //反轉(zhuǎn)后新鏈表的表頭 while (current != null) { next = current.next; //暫時(shí)保存住當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，因?yàn)橄乱淮我? current.next = reverseHead; //將current的下一個(gè)結(jié)點(diǎn)指向新鏈表的頭結(jié)點(diǎn) reverseHead = current; current = next; // 操作結(jié)束后，current節(jié)點(diǎn)后移 } return reverseHead; }
上方代碼中，核心代碼是第16、17行。
方法2：（遞歸）
這個(gè)方法有點(diǎn)難，先不講了。
7、從尾到頭打印單鏈表：
對于這種顛倒順序的問題，我們應(yīng)該就會想到棧，后進(jìn)先出。所以，這一題要么自己使用棧，要么讓系統(tǒng)使用棧，也就是遞歸。注意鏈表為空的情況。時(shí)間復(fù)雜度為O（n）
注：不要想著先將單鏈表反轉(zhuǎn)，然后遍歷輸出，這樣會破壞鏈表的結(jié)構(gòu)，不建議。
方法1：（自己新建一個(gè)棧）
//方法：從尾到頭打印單鏈表 public void reversePrint(Node head) { if (head == null) { return; } Stackstack = new Stack(); //新建一個(gè)棧 Node current = head; //將鏈表的所有結(jié)點(diǎn)壓棧 while (current != null) {- stack.push(current); //將當(dāng)前結(jié)點(diǎn)壓棧 current = current.next; } //將棧中的結(jié)點(diǎn)打印輸出即可 while (stack.size() > 0) { System.out.println(stack.pop().data); //出棧操作 } }
方法2：（使用系統(tǒng)的棧：遞歸，代碼優(yōu)雅簡潔）
public void reversePrint(Node head) { if (head == null) { return; } reversePrint(head.next); System.out.println(head.data); }
總結(jié)：方法2是基于遞歸實(shí)現(xiàn)的，戴安看起來簡潔優(yōu)雅，但有個(gè)問題：當(dāng)鏈表很長的時(shí)候，就會導(dǎo)致方法調(diào)用的層級很深，有可能造成棧溢出。而方法1的顯式用棧，是基于循環(huán)實(shí)現(xiàn)的，代碼的魯棒性要更好一些。
8、判斷單鏈表是否有環(huán)：
這里也是用到兩個(gè)指針，如果一個(gè)鏈表有環(huán)，那么用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的。
因此，我們用兩個(gè)指針去遍歷：first指針每次走一步，second指針每次走兩步，如果first指針和second指針相遇，說明有環(huán)。時(shí)間復(fù)雜度為O (n)。
方法：
//方法：判斷單鏈表是否有環(huán) public boolean hasCycle(Node head) { if (head == null) { return false; } Node first = head; Node second = head; while (second != null) { first = first.next; //first指針走一步 second = second.next.next; second指針走兩步 if (first == second) { //一旦兩個(gè)指針相遇，說明鏈表是有環(huán)的 return true; } } return false; }
完整版代碼：（包含測試部分）
這里，我們還需要加一個(gè)重載的add(Node node)方法，在創(chuàng)建單向循環(huán)鏈表時(shí)要用到。
LinkList.java: public class LinkList { public Node head; public Node current; //方法：向鏈表中添加數(shù)據(jù) public void add(int data) { //判斷鏈表為空的時(shí)候 if (head == null) {//如果頭結(jié)點(diǎn)為空，說明這個(gè)鏈表還沒有創(chuàng)建，那就把新的結(jié)點(diǎn)賦給頭結(jié)點(diǎn) head = new Node(data); current = head; } else { //創(chuàng)建新的結(jié)點(diǎn)，放在當(dāng)前節(jié)點(diǎn)的后面（把新的結(jié)點(diǎn)合鏈表進(jìn)行關(guān)聯(lián)） current.next = new Node(data); //把鏈表的當(dāng)前索引向后移動一位 current = current.next; } } //方法重載：向鏈表中添加結(jié)點(diǎn) public void add(Node node) { if (node == null) { return; } if (head == null) { head = node; current = head; } else { current.next = node; current = current.next; } } //方法：遍歷鏈表（打印輸出鏈表。方法的參數(shù)表示從節(jié)點(diǎn)node開始進(jìn)行遍歷 public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //方法：檢測單鏈表是否有環(huán) public boolean hasCycle(Node head) { if (head == null) { return false; } Node first = head; Node second = head; while (second != null) { first = first.next; //first指針走一步 second = second.next.next; //second指針走兩步 if (first == second) { //一旦兩個(gè)指針相遇，說明鏈表是有環(huán)的 return true; } } return false; } class Node { //注：此處的兩個(gè)成員變量權(quán)限不能為private，因?yàn)閜rivate的權(quán)限是僅對本類訪問。 int data; //數(shù)據(jù)域 Node next;//指針域 public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list = new LinkList(); //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 4; i++) { list.add(i); } list.add(list.head); //將頭結(jié)點(diǎn)添加到鏈表當(dāng)中，于是，單鏈表就有環(huán)了。備注：此時(shí)得到的這個(gè)環(huán)的結(jié)構(gòu)，是下面的第8小節(jié)中圖1的那種結(jié)構(gòu)。 System.out.println(list.hasCycle(list.head)); } }
檢測單鏈表是否有環(huán)的代碼是第50行。
88行：我們將頭結(jié)點(diǎn)繼續(xù)往鏈表中添加，此時(shí)單鏈表就環(huán)了。最終運(yùn)行效果為true。
如果刪掉了88行代碼，此時(shí)單鏈表沒有環(huán)，運(yùn)行效果為false。
9、取出有環(huán)鏈表中，環(huán)的長度：
那怎么求出環(huán)的長度呢？
思路：
這里面，我們需要先利用上面的第7小節(jié)中的hasCycle方法（判斷鏈表是否有環(huán)的那個(gè)方法），這個(gè)方法的返回值是boolean型，但是現(xiàn)在要把這個(gè)方法稍做修改，讓其返回值為相遇的那個(gè)結(jié)點(diǎn)。然后，我們拿到這個(gè)相遇的結(jié)點(diǎn)就好辦了，這個(gè)結(jié)點(diǎn)肯定是在環(huán)里嘛，我們可以讓這個(gè)結(jié)點(diǎn)對應(yīng)的指針一直往下走，直到它回到原點(diǎn)，就可以算出環(huán)的長度了。
方法：
//方法：判斷單鏈表是否有環(huán)。返回的結(jié)點(diǎn)是相遇的那個(gè)結(jié)點(diǎn) public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //一旦兩個(gè)指針相遇，說明鏈表是有環(huán)的 return first; //將相遇的那個(gè)結(jié)點(diǎn)進(jìn)行返回 } } return null; } //方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個(gè)結(jié)點(diǎn) public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != null) { current = current.next; length++; if (current == node) { //當(dāng)current結(jié)點(diǎn)走到原點(diǎn)的時(shí)候 return length; } } return length; }
完整版代碼：（包含測試部分）
public class LinkList { public Node head; public Node current; public int size; //方法：向鏈表中添加數(shù)據(jù) public void add(int data) { //判斷鏈表為空的時(shí)候 if (head == null) {//如果頭結(jié)點(diǎn)為空，說明這個(gè)鏈表還沒有創(chuàng)建，那就把新的結(jié)點(diǎn)賦給頭結(jié)點(diǎn) head = new Node(data); current = head; } else { //創(chuàng)建新的結(jié)點(diǎn)，放在當(dāng)前節(jié)點(diǎn)的后面（把新的結(jié)點(diǎn)合鏈表進(jìn)行關(guān)聯(lián)） current.next = new Node(data); //把鏈表的.當(dāng)前索引向后移動一位 current = current.next; //此步操作完成之后，current結(jié)點(diǎn)指向新添加的那個(gè)結(jié)點(diǎn) } } //方法重載：向鏈表中添加結(jié)點(diǎn) public void add(Node node) { if (node == null) { return; } if (head == null) { head = node; current = head; } else { current.next = node; current = current.next; } } //方法：遍歷鏈表（打印輸出鏈表。方法的參數(shù)表示從節(jié)點(diǎn)node開始進(jìn)行遍歷 public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //方法：判斷單鏈表是否有環(huán)。返回的結(jié)點(diǎn)是相遇的那個(gè)結(jié)點(diǎn) public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //一旦兩個(gè)指針相遇，說明鏈表是有環(huán)的 return first; //將相遇的那個(gè)結(jié)點(diǎn)進(jìn)行返回 } } return null; } //方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個(gè)結(jié)點(diǎn) public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != null) { current = current.next; length++; if (current == node) { //當(dāng)current結(jié)點(diǎn)走到原點(diǎn)的時(shí)候 return length; } } return length; } class Node { //注：此處的兩個(gè)成員變量權(quán)限不能為private，因?yàn)閜rivate的權(quán)限是僅對本類訪問。 int data; //數(shù)據(jù)域 Node next;//指針域 public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list1 = new LinkList(); Node second = null; //把第二個(gè)結(jié)點(diǎn)記下來 //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 4; i++) { list1.add(i); if (i == 1) { second = list1.current; //把第二個(gè)結(jié)點(diǎn)記下來 } } list1.add(second); //將尾結(jié)點(diǎn)指向鏈表的第二個(gè)結(jié)點(diǎn)，于是單鏈表就有環(huán)了，備注：此時(shí)得到的環(huán)的結(jié)構(gòu)，是本節(jié)中圖2的那種結(jié)構(gòu) Node current = list1.hasCycle(list1.head); //獲取相遇的那個(gè)結(jié)點(diǎn) System.out.println("環(huán)的長度為" + list1.getCycleLength(current)); } }
如果將上面的104至122行的測試代碼改成下面這樣的：
public static void main(String[] args) { LinkList list1 = new LinkList(); //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 4; i++) { list1.add(i); } list1.add(list1.head); //將頭結(jié)點(diǎn)添加到鏈表當(dāng)中（將尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)），于是，單鏈表就有環(huán)了。備注：此時(shí)得到的這個(gè)環(huán)的結(jié)構(gòu)，是本節(jié)中圖1的那種結(jié)構(gòu)。 Node current = list1.hasCycle(list1.head); System.out.println("環(huán)的長度為" + list1.getCycleLength(current)); }
如果把上面的代碼中的第8行刪掉，那么這個(gè)鏈表就沒有環(huán)了，于是運(yùn)行的結(jié)果為0。
10、單鏈表中，取出環(huán)的起始點(diǎn)：
方法1：
這里我們需要利用到上面第8小節(jié)的取出環(huán)的長度的方法getCycleLength，用這個(gè)方法來獲取環(huán)的長度length。拿到環(huán)的長度length之后，需要用到兩個(gè)指針變量first和second，先讓second指針走length步；然后讓first指針和second指針同時(shí)各走一步，當(dāng)兩個(gè)指針相遇時(shí)，相遇時(shí)的結(jié)點(diǎn)就是環(huán)的起始點(diǎn)。
注：為了找到環(huán)的起始點(diǎn)，我們需要先獲取環(huán)的長度，而為了獲取環(huán)的長度，我們需要先判斷是否有環(huán)。所以這里面其實(shí)是用到了三個(gè)方法。
代碼實(shí)現(xiàn)：
方法1的核心代碼：
//方法：獲取環(huán)的起始點(diǎn)。參數(shù)length表示環(huán)的長度 public Node getCycleStart(Node head, int cycleLength) { if (head == null) { return null; } Node first = head; Node second = head; //先讓second指針走length步 for (int i = 0; i < cycleLength; i++) { second = second.next; } //然后讓first指針和second指針同時(shí)各走一步 while (first != null && second != null) { first = first.next; second = second.next; if (first == second) { //如果兩個(gè)指針相遇了，說明這個(gè)結(jié)點(diǎn)就是環(huán)的起始點(diǎn) return first; } } return null; }
完整版代碼：（含測試部分）
public class LinkList { public Node head; public Node current; public int size; //方法：向鏈表中添加數(shù)據(jù) public void add(int data) { //判斷鏈表為空的時(shí)候 if (head == null) {//如果頭結(jié)點(diǎn)為空，說明這個(gè)鏈表還沒有創(chuàng)建，那就把新的結(jié)點(diǎn)賦給頭結(jié)點(diǎn) head = new Node(data); current = head; } else { //創(chuàng)建新的結(jié)點(diǎn)，放在當(dāng)前節(jié)點(diǎn)的后面（把新的結(jié)點(diǎn)合鏈表進(jìn)行關(guān)聯(lián)） current.next = new Node(data); //把鏈表的當(dāng)前索引向后移動一位 current = current.next; //此步操作完成之后，current結(jié)點(diǎn)指向新添加的那個(gè)結(jié)點(diǎn) } } //方法重載：向鏈表中添加結(jié)點(diǎn) public void add(Node node) { if (node == null) { return; } if (head == null) { head = node; current = head; } else { current.next = node; current = current.next; } } //方法：遍歷鏈表（打印輸出鏈表。方法的參數(shù)表示從節(jié)點(diǎn)node開始進(jìn)行遍歷 public void print(Node node) { if (node == null) { return; } current = node; while (current != null) { System.out.println(current.data); current = current.next; } } //方法：判斷單鏈表是否有環(huán)。返回的結(jié)點(diǎn)是相遇的那個(gè)結(jié)點(diǎn) public Node hasCycle(Node head) { if (head == null) { return null; } Node first = head; Node second = head; while (second != null) { first = first.next; second = second.next.next; if (first == second) { //一旦兩個(gè)指針相遇，說明鏈表是有環(huán)的 return first; //將相遇的那個(gè)結(jié)點(diǎn)進(jìn)行返回 } } return null; } //方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個(gè)結(jié)點(diǎn) public int getCycleLength(Node node) { if (head == null) { return 0; } Node current = node; int length = 0; while (current != null) { current = current.next; length++; if (current == node) { //當(dāng)current結(jié)點(diǎn)走到原點(diǎn)的時(shí)候 return length; } } return length; } //方法：獲取環(huán)的起始點(diǎn)。參數(shù)length表示環(huán)的長度 public Node getCycleStart(Node head, int cycleLength) { if (head == null) { return null; } Node first = head; Node second = head; //先讓second指針走length步 for (int i = 0; i < cycleLength; i++) { second = second.next; } //然后讓first指針和second指針同時(shí)各走一步 while (first != null && second != null) { first = first.next; second = second.next; if (first == second) { //如果兩個(gè)指針相遇了，說明這個(gè)結(jié)點(diǎn)就是環(huán)的起始點(diǎn) return first; } } return null; } class Node { //注：此處的兩個(gè)成員變量權(quán)限不能為private，因?yàn)閜rivate的權(quán)限是僅對本類訪問。 int data; //數(shù)據(jù)域 Node next;//指針域 public Node(int data) { this.data = data; } } public static void main(String[] args) { LinkList list1 = new LinkList(); Node second = null; //把第二個(gè)結(jié)點(diǎn)記下來 //向LinkList中添加數(shù)據(jù) for (int i = 0; i < 4; i++) { list1.add(i); if (i == 1) { second = list1.current; //把第二個(gè)結(jié)點(diǎn)記下來 } } list1.add(second); //將尾結(jié)點(diǎn)指向鏈表的第二個(gè)結(jié)點(diǎn)，于是單鏈表就有環(huán)了，備注：此時(shí)得到的環(huán)的結(jié)構(gòu)，是本節(jié)中圖2的那種結(jié)構(gòu) Node current = list1.hasCycle(list1.head); //獲取相遇的那個(gè)結(jié)點(diǎn) int length = list1.getCycleLength(current); //獲取環(huán)的長度 System.out.println("環(huán)的起始點(diǎn)是" + list1.getCycleStart(list1.head, length).data); } }
11、判斷兩個(gè)單鏈表相交的第一個(gè)交點(diǎn)：
《編程之美》P193，5.3，面試題37就有這道題。
面試時(shí)，很多人碰到這道題的第一反應(yīng)是：在第一個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)，每遍歷到一個(gè)結(jié)點(diǎn)的時(shí)候，在第二個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。如果在第二個(gè)鏈表上有一個(gè)結(jié)點(diǎn)和第一個(gè)鏈表上的結(jié)點(diǎn)一樣，說明兩個(gè)鏈表在這個(gè)結(jié)點(diǎn)上重合。顯然該方法的時(shí)間復(fù)雜度為O(len1 * len2)。
方法1：采用棧的思路
如果單鏈表有公共結(jié)點(diǎn)，那么最后一個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)7）一定是一樣的，而且是從中間的某一個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)6）開始，后續(xù)的結(jié)點(diǎn)都是一樣的。
現(xiàn)在的問題是，在單鏈表中，我們只能從頭結(jié)點(diǎn)開始順序遍歷，最后才能到達(dá)尾結(jié)點(diǎn)。最后到達(dá)的尾節(jié)點(diǎn)卻要先被比較，這聽起來是不是像“先進(jìn)后出”？于是我們就能想到利用棧的特點(diǎn)來解決這個(gè)問題：分別把兩個(gè)鏈表的結(jié)點(diǎn)放入兩個(gè)棧中，這樣兩個(gè)鏈表的尾結(jié)點(diǎn)就位于兩個(gè)棧的棧頂，接下來比較下一個(gè)棧頂，直到找到最后一個(gè)相同的結(jié)點(diǎn)。
這種思路中，我們需要利用兩個(gè)輔助棧，空間復(fù)雜度是O(len1+len2)，時(shí)間復(fù)雜度是O(len1+len2)。和一開始的蠻力法相比，時(shí)間效率得到了提高，相當(dāng)于是利用空間消耗換取時(shí)間效率。
那么，有沒有更好的方法呢？接下來要講。
方法2：判斷兩個(gè)鏈表相交的第一個(gè)結(jié)點(diǎn)：用到快慢指針，推薦（更優(yōu)解）
我們在上面的方法2中，之所以用到棧，是因?yàn)槲覀兿胪瑫r(shí)遍歷到達(dá)兩個(gè)鏈表的尾結(jié)點(diǎn)。其實(shí)為解決這個(gè)問題我們還有一個(gè)更簡單的辦法：首先遍歷兩個(gè)鏈表得到它們的長度。在第二次遍歷的時(shí)候，在較長的鏈表上走 |len1-len2| 步，接著再同時(shí)在兩個(gè)鏈表上遍歷，找到的第一個(gè)相同的結(jié)點(diǎn)就是它們的第一個(gè)交點(diǎn)。
這種思路的時(shí)間復(fù)雜度也是O(len1+len2)，但是我們不再需要輔助棧，因此提高了空間效率。當(dāng)面試官肯定了我們的最后一種思路的時(shí)候，就可以動手寫代碼了。
核心代碼：
//方法：求兩個(gè)單鏈表相交的第一個(gè)交點(diǎn) public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = getLength(head1); int length2 = getLength(head2); int lengthDif = 0; //兩個(gè)鏈表長度的差值 Node longHead; Node shortHead; //找出較長的那個(gè)鏈表 if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //將較長的那個(gè)鏈表的指針向前走length個(gè)距離 for (int i = 0; i < lengthDif; i++) { longHead = longHead.next; } //將兩個(gè)鏈表的指針同時(shí)向前移動 while (longHead != null && shortHead != null) { if (longHead == shortHead) { //第一個(gè)相同的結(jié)點(diǎn)就是相交的第一個(gè)結(jié)點(diǎn) return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //方法：獲取單鏈表的長度 public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length;
以上就是有關(guān)java鏈表的經(jīng)典面試題目，希望可以幫助大家順利通過面試。
【最新JAVA實(shí)現(xiàn)鏈表面試題】相關(guān)文章：
2016java面試題（最新）02-02
java面試題01-31
java學(xué)習(xí)：Java面試題和答案07-23
Java經(jīng)典面試題05-06
Java面試題集07-19
java面試題匯總08-23
java基礎(chǔ)面試題02-26
常見java面試題02-25
Java框架面試題07-09