JAVA實現(xiàn)鏈表面試題
這份筆記整理了整整一個星期，每一行代碼都是自己默寫完成，并測試運行成功，同時也回顧了一下《劍指offer》這本書中和鏈表有關(guān)的講解，希望對筆試和面試有所幫助。
本文包含鏈表的以下內(nèi)容：
1、單鏈表的創(chuàng)建和遍歷
2、求單鏈表中節(jié)點的個數(shù)
3、查找單鏈表中的倒數(shù)第k個結(jié)點（劍指offer，題15）
4、查找單鏈表中的中間結(jié)點
5、合并兩個有序的單鏈表，合并之后的鏈表依然有序【出現(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)的起始點（劍指offer，題56）。本題需利用上面的第8題和第9題。
11、判斷兩個單鏈表相交的第一個交點（劍指offer，題37）
1、單鏈表的創(chuàng)建和遍歷：
public class LinkList {
public Node head;
public Node current;
//方法：向鏈表中添加數(shù)據(jù)
public void add(int data) {
//判斷鏈表為空的時候
if (head == null) {//如果頭結(jié)點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結(jié)點賦給頭結(jié)點
head = new Node(data);
current = head;
} else {
//創(chuàng)建新的結(jié)點，放在當前節(jié)點的后面（把新的結(jié)點合鏈表進行關(guān)聯(lián)）
current.next = new Node(data);
//把鏈表的當前索引向后移動一位
current = current.next; //此步操作完成之后，current結(jié)點指向新添加的那個結(jié)點
}
}
//方法：遍歷鏈表（打印輸出鏈表。方法的參數(shù)表示從節(jié)點node開始進行遍歷
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
class Node {
//注：此處的兩個成員變量權(quán)限不能為private，因為private的權(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é)點開始遍歷輸出
}
}
上方代碼中，這里面的Node節(jié)點采用的是內(nèi)部類來表示（33行）。使用內(nèi)部類的最大好處是可以和外部類進行私有操作的互相訪問。
注：內(nèi)部類訪問的特點是：內(nèi)部類可以直接訪問外部類的成員，包括私有；外部類要訪問內(nèi)部類的成員，必須先創(chuàng)建對象。
為了方便添加和遍歷的操作，在LinkList類中添加一個成員變量current，用來表示當前節(jié)點的索引（03行）。
這里面的遍歷鏈表的方法（20行）中，參數(shù)node表示從node節(jié)點開始遍歷，不一定要從head節(jié)點遍歷。
2、求單鏈表中節(jié)點的個數(shù)：
注意檢查鏈表是否為空。時間復雜度為O（n）。這個比較簡單。
核心代碼：
//方法：獲取單鏈表的長度
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個結(jié)點：
3.1 普通思路：
先將整個鏈表從頭到尾遍歷一次，計算出鏈表的長度size，得到鏈表的長度之后，就好辦了，直接輸出第(size-k)個節(jié)點就可以了（注意鏈表為空，k為0，k為1，k大于鏈表中節(jié)點個數(shù)時的情況）。時間復雜度為O（n），大概思路如下：
public int findLastNode(int index) { //index代表的是倒數(shù)第index的那個結(jié)點
//第一次遍歷，得到鏈表的長度size
if (head == null) {
return -1;
}
current = head;
while (current != null) {
size++;
current = current.next;
}
//第二次遍歷，輸出倒數(shù)第index個結(jié)點的數(shù)據(jù)
current = head;
for (int i = 0; i < size - index; i++) {
current = current.next;
}
return current.data;
}
如果面試官不允許你遍歷鏈表的長度，該怎么做呢？接下來就是。
3.2 改進思路：（這種思路在其他題目中也有應用）
這里需要聲明兩個指針：即兩個結(jié)點型的變量first和second，首先讓first和second都指向第一個結(jié)點，然后讓second結(jié)點往后挪k-1個位置，此時first和second就間隔了k-1個位置，然后整體向后移動這兩個節(jié)點，直到second節(jié)點走到最后一個結(jié)點的時候，此時first節(jié)點所指向的位置就是倒數(shù)第k個節(jié)點的位置。時間復雜度為O（n）
代碼實現(xiàn)：（初版）
public Node findLastNode(Node head, int index) {
if (node == null) {
return null;
}
Node first = head;
Node second = head;
//讓second結(jié)點往后挪index個位置
for (int i = 0; i < index; i++) {
second = second.next;
}
//讓first和second結(jié)點整體向后移動，直到second結(jié)點為Null
while (second != null) {
first = first.next;
second = second.next;
}
//當second結(jié)點為空的時候，此時first指向的結(jié)點就是我們要找的結(jié)點
return first;
}代碼實現(xiàn)：（最終版）（考慮k大于鏈表中結(jié)點個數(shù)時的情況時，拋出異常）
上面的代碼中，看似已經(jīng)實現(xiàn)了功能，其實還不夠健壯:
要注意k等于0的情況；
如果k大于鏈表中節(jié)點個數(shù)時，就會報空指針異常，所以這里需要做一下判斷。
核心代碼如下：
public Node findLastNode(Node head, int k) {
if (k == 0 || head == null) {
return null;
}
Node first = head;
Node second = head;
//讓second結(jié)點往后挪k-1個位置
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é)點整體向后移動，直到second走到最后一個結(jié)點
while (second.next != null) {
first = first.next;
second = second.next;
}
//當second結(jié)點走到最后一個節(jié)點的時候，此時first指向的結(jié)點就是我們要找的結(jié)點
return first;
}
4、查找單鏈表中的中間結(jié)點：
同樣，面試官不允許你算出鏈表的長度，該怎么做呢？
思路：
和上面的第2節(jié)一樣，也是設置兩個指針first和second，只不過這里是，兩個指針同時向前走，second指針每次走兩步，first指針每次走一步，直到second指針走到最后一個結(jié)點時，此時first指針所指的結(jié)點就是中間結(jié)點。注意鏈表為空，鏈表結(jié)點個數(shù)為1和2的情況。時間復雜度為O（n）。
代碼實現(xiàn)：
//方法：查找鏈表的中間結(jié)點
public Node findMidNode(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//每次移動時，讓second結(jié)點移動兩位，first結(jié)點移動一位
while (second != null && second.next != null) {
first = first.next;
second = second.next.next;
}
//直到second結(jié)點移動到null時，此時first指針指向的位置就是中間結(jié)點的位置
return first;
}
上方代碼中，當n為偶數(shù)時，得到的中間結(jié)點是第n/2 + 1個結(jié)點。比如鏈表有6個節(jié)點時，得到的是第4個節(jié)點。
5、合并兩個有序的單鏈表，合并之后的鏈表依然有序：
這道題經(jīng)常被各公司考察。
例如：
鏈表1：
1->2->3->4
鏈表2：
2->3->4->5
合并后：
1->2->2->3->3->4->4->5
解題思路：
挨著比較鏈表1和鏈表2。
這個類似于歸并排序。尤其要注意兩個鏈表都為空、和其中一個為空的情況。只需要O (1) 的空間。時間復雜度為O (max(len1,len2))
代碼實現(xiàn)：
//兩個參數(shù)代表的是兩個鏈表的頭結(jié)點
public Node mergeLinkList(Node head1, Node head2) {
if (head1 == null && head2 == null) { //如果兩個鏈表都為空
return null;
}
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node head; //新鏈表的頭結(jié)點
Node current; //current結(jié)點指向新鏈表
// 一開始，我們讓current結(jié)點指向head1和head2中較小的數(shù)據(jù)，得到head結(jié)點
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指針的下一個結(jié)點對應較小的那個數(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é)點開始遍歷輸出
}
上方代碼中用到的add方法和print方法和第1小節(jié)中是一致的。
運行效果：
注：《劍指offer》中是用遞歸解決的，感覺有點難理解。
6、單鏈表的反轉(zhuǎn)：【出現(xiàn)頻率最高】
例如鏈表：
1->2->3->4
反轉(zhuǎn)之后：
4->2->2->1
思路：
從頭到尾遍歷原鏈表，每遍歷一個結(jié)點，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個結(jié)點的情況。時間復雜度為O（n）
方法1：（遍歷）
//方法：鏈表的反轉(zhuǎn)
public Node reverseList(Node head) {
//如果鏈表為空或者只有一個節(jié)點，無需反轉(zhuǎn)，直接返回原鏈表的頭結(jié)點
if (head == null || head.next == null) {
return head;
}
Node current = head;
Node next = null; //定義當前結(jié)點的下一個結(jié)點
Node reverseHead = null; //反轉(zhuǎn)后新鏈表的表頭
while (current != null) {
next = current.next; //暫時保存住當前結(jié)點的下一個結(jié)點，因為下一次要用
current.next = reverseHead; //將current的下一個結(jié)點指向新鏈表的頭結(jié)點
reverseHead = current;
current = next; // 操作結(jié)束后，current節(jié)點后移
}
return reverseHead;
}
上方代碼中，核心代碼是第16、17行。
方法2：（遞歸）
這個方法有點難，先不講了。
7、從尾到頭打印單鏈表：
對于這種顛倒順序的問題，我們應該就會想到棧，后進先出。所以，這一題要么自己使用棧，要么讓系統(tǒng)使用棧，也就是遞歸。注意鏈表為空的情況。時間復雜度為O（n）
注：不要想著先將單鏈表反轉(zhuǎn)，然后遍歷輸出，這樣會破壞鏈表的結(jié)構(gòu)，不建議。
方法1：（自己新建一個棧）
//方法：從尾到頭打印單鏈表
public void reversePrint(Node head) {
if (head == null) {
return;
}
Stack<Node> stack = new Stack<Node>(); //新建一個棧
Node current = head;
//將鏈表的所有結(jié)點壓棧
while (current != null) {-
stack.push(current); //將當前結(jié)點壓棧
current = current.next;
}
//將棧中的結(jié)點打印輸出即可
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是基于遞歸實現(xiàn)的，戴安看起來簡潔優(yōu)雅，但有個問題：當鏈表很長的時候，就會導致方法調(diào)用的層級很深，有可能造成棧溢出。而方法1的顯式用棧，是基于循環(huán)實現(xiàn)的，代碼的魯棒性要更好一些。
8、判斷單鏈表是否有環(huán)：
這里也是用到兩個指針，如果一個鏈表有環(huán)，那么用一個指針去遍歷，是永遠走不到頭的。
因此，我們用兩個指針去遍歷：first指針每次走一步，second指針每次走兩步，如果first指針和second指針相遇，說明有環(huán)。時間復雜度為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) { //一旦兩個指針相遇，說明鏈表是有環(huán)的
return true;
}
}
return false;
}
完整版代碼：（包含測試部分）
這里，我們還需要加一個重載的add(Node node)方法，在創(chuàng)建單向循環(huán)鏈表時要用到。
LinkList.java:
public class LinkList {
public Node head;
public Node current;
//方法：向鏈表中添加數(shù)據(jù)
public void add(int data) {
//判斷鏈表為空的時候
if (head == null) {//如果頭結(jié)點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結(jié)點賦給頭結(jié)點
head = new Node(data);
current = head;
} else {
//創(chuàng)建新的結(jié)點，放在當前節(jié)點的后面（把新的結(jié)點合鏈表進行關(guān)聯(lián)）
current.next = new Node(data);
//把鏈表的當前索引向后移動一位
current = current.next;
}
}
//方法重載：向鏈表中添加結(jié)點
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é)點node開始進行遍歷
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) { //一旦兩個指針相遇，說明鏈表是有環(huán)的
return true;
}
}
return false;
}
class Node {
//注：此處的兩個成員變量權(quán)限不能為private，因為private的權(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é)點添加到鏈表當中，于是，單鏈表就有環(huán)了。備注：此時得到的這個環(huán)的結(jié)構(gòu)，是下面的第8小節(jié)中圖1的那種結(jié)構(gòu)。
System.out.println(list.hasCycle(list.head));
}
}
檢測單鏈表是否有環(huán)的代碼是第50行。
88行：我們將頭結(jié)點繼續(xù)往鏈表中添加，此時單鏈表就環(huán)了。最終運行效果為true。
如果刪掉了88行代碼，此時單鏈表沒有環(huán)，運行效果為false。
9、取出有環(huán)鏈表中，環(huán)的長度：
我們平時碰到的有環(huán)鏈表是下面的這種：（圖1）
上圖中環(huán)的長度是4。
但有可能也是下面的這種：（圖2）
此時，上圖中環(huán)的長度就是3了。
那怎么求出環(huán)的長度呢？
思路：
這里面，我們需要先利用上面的第7小節(jié)中的hasCycle方法（判斷鏈表是否有環(huán)的那個方法），這個方法的返回值是boolean型，但是現(xiàn)在要把這個方法稍做修改，讓其返回值為相遇的那個結(jié)點。然后，我們拿到這個相遇的結(jié)點就好辦了，這個結(jié)點肯定是在環(huán)里嘛，我們可以讓這個結(jié)點對應的指針一直往下走，直到它回到原點，就可以算出環(huán)的長度了。
方法：
//方法：判斷單鏈表是否有環(huán)。返回的結(jié)點是相遇的那個結(jié)點
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) { //一旦兩個指針相遇，說明鏈表是有環(huán)的
return first; //將相遇的那個結(jié)點進行返回
}
}
return null;
}
//方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個結(jié)點
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) { //當current結(jié)點走到原點的時候
return length;
}
}
return length;
}
完整版代碼：（包含測試部分）
public class LinkList {
public Node head;
public Node current;
public int size;
//方法：向鏈表中添加數(shù)據(jù)
public void add(int data) {
//判斷鏈表為空的時候
if (head == null) {//如果頭結(jié)點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結(jié)點賦給頭結(jié)點
head = new Node(data);
current = head;
} else {
//創(chuàng)建新的結(jié)點，放在當前節(jié)點的后面（把新的結(jié)點合鏈表進行關(guān)聯(lián)）
current.next = new Node(data);
//把鏈表的當前索引向后移動一位
current = current.next; //此步操作完成之后，current結(jié)點指向新添加的那個結(jié)點
}
}
//方法重載：向鏈表中添加結(jié)點
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é)點node開始進行遍歷
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é)點是相遇的那個結(jié)點
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) { //一旦兩個指針相遇，說明鏈表是有環(huán)的
return first; //將相遇的那個結(jié)點進行返回
}
}
return null;
}
//方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個結(jié)點
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) { //當current結(jié)點走到原點的時候
return length;
}
}
return length;
}
class Node {
//注：此處的兩個成員變量權(quán)限不能為private，因為private的權(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; //把第二個結(jié)點記下來
//向LinkList中添加數(shù)據(jù)
for (int i = 0; i < 4; i++) {
list1.add(i);
if (i == 1) {
second = list1.current; //把第二個結(jié)點記下來
}
}
list1.add(second); //將尾結(jié)點指向鏈表的第二個結(jié)點，于是單鏈表就有環(huán)了，備注：此時得到的環(huán)的結(jié)構(gòu)，是本節(jié)中圖2的那種結(jié)構(gòu)
Node current = list1.hasCycle(list1.head); //獲取相遇的那個結(jié)點
System.out.println("環(huán)的長度為" + list1.getCycleLength(current));
}
}運行效果：
如果將上面的104至122行的測試代碼改成下面這樣的：（即：將圖2中的結(jié)構(gòu)改成圖1中的結(jié)構(gòu)）
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é)點添加到鏈表當中（將尾結(jié)點指向頭結(jié)點），于是，單鏈表就有環(huán)了。備注：此時得到的這個環(huán)的結(jié)構(gòu)，是本節(jié)中圖1的那種結(jié)構(gòu)。
Node current = list1.hasCycle(list1.head);
System.out.println("環(huán)的長度為" + list1.getCycleLength(current));
}
運行結(jié)果：
如果把上面的代碼中的第8行刪掉，那么這個鏈表就沒有環(huán)了，于是運行的結(jié)果為0。
10、單鏈表中，取出環(huán)的起始點：
我們平時碰到的有環(huán)鏈表是下面的這種：（圖1）
上圖中環(huán)的起始點1。
但有可能也是下面的這種：（圖2）
此時，上圖中環(huán)的起始點是2。
方法1：
這里我們需要利用到上面第8小節(jié)的取出環(huán)的長度的方法getCycleLength，用這個方法來獲取環(huán)的長度length。拿到環(huán)的長度length之后，需要用到兩個指針變量first和second，先讓second指針走length步；然后讓first指針和second指針同時各走一步，當兩個指針相遇時，相遇時的結(jié)點就是環(huán)的起始點。
注：為了找到環(huán)的起始點，我們需要先獲取環(huán)的長度，而為了獲取環(huán)的長度，我們需要先判斷是否有環(huán)。所以這里面其實是用到了三個方法。
代碼實現(xiàn)：
方法1的核心代碼：
//方法：獲取環(huá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指針同時各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //如果兩個指針相遇了，說明這個結(jié)點就是環(huán)的起始點
return first;
}
}
return null;
}
完整版代碼：（含測試部分）
public class LinkList {
public Node head;
public Node current;
public int size;
//方法：向鏈表中添加數(shù)據(jù)
public void add(int data) {
//判斷鏈表為空的時候
if (head == null) {//如果頭結(jié)點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結(jié)點賦給頭結(jié)點
head = new Node(data);
current = head;
} else {
//創(chuàng)建新的結(jié)點，放在當前節(jié)點的后面（把新的結(jié)點合鏈表進行關(guān)聯(lián)）
current.next = new Node(data);
//把鏈表的當前索引向后移動一位
current = current.next; //此步操作完成之后，current結(jié)點指向新添加的那個結(jié)點
}
}
//方法重載：向鏈表中添加結(jié)點
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é)點node開始進行遍歷
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é)點是相遇的那個結(jié)點
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) { //一旦兩個指針相遇，說明鏈表是有環(huán)的
return first; //將相遇的那個結(jié)點進行返回
}
}
return null;
}
//方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個結(jié)點
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) { //當current結(jié)點走到原點的時候
return length;
}
}
return length;
}
//方法：獲取環(huá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指針同時各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //如果兩個指針相遇了，說明這個結(jié)點就是環(huán)的起始點
return first;
}
}
return null;
}
class Node {
//注：此處的兩個成員變量權(quán)限不能為private，因為private的權(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; //把第二個結(jié)點記下來
//向LinkList中添加數(shù)據(jù)
for (int i = 0; i < 4; i++) {
list1.add(i);
if (i == 1) {
second = list1.current; //把第二個結(jié)點記下來
}
}
list1.add(second); //將尾結(jié)點指向鏈表的第二個結(jié)點，于是單鏈表就有環(huán)了，備注：此時得到的環(huán)的結(jié)構(gòu)，是本節(jié)中圖2的那種結(jié)構(gòu)
Node current = list1.hasCycle(list1.head); //獲取相遇的那個結(jié)點
int length = list1.getCycleLength(current); //獲取環(huán)的長度
System.out.println("環(huán)的起始點是" + list1.getCycleStart(list1.head, length).data);
}
}
11、判斷兩個單鏈表相交的第一個交點：
《編程之美》P193，5.3，面試題37就有這道題。
面試時，很多人碰到這道題的第一反應是：在第一個鏈表上順序遍歷每個結(jié)點，每遍歷到一個結(jié)點的時候，在第二個鏈表上順序遍歷每個結(jié)點。如果在第二個鏈表上有一個結(jié)點和第一個鏈表上的結(jié)點一樣，說明兩個鏈表在這個結(jié)點上重合。顯然該方法的時間復雜度為O(len1 * len2)。
方法1：采用棧的思路
我們可以看出兩個有公共結(jié)點而部分重合的鏈表，拓撲形狀看起來像一個Y，而不可能是X型。 如下圖所示：
如上圖所示，如果單鏈表有公共結(jié)點，那么最后一個結(jié)點（結(jié)點7）一定是一樣的，而且是從中間的某一個結(jié)點（結(jié)點6）開始，后續(xù)的結(jié)點都是一樣的。
現(xiàn)在的問題是，在單鏈表中，我們只能從頭結(jié)點開始順序遍歷，最后才能到達尾結(jié)點。最后到達的尾節(jié)點卻要先被比較，這聽起來是不是像“先進后出”？于是我們就能想到利用棧的特點來解決這個問題：分別把兩個鏈表的結(jié)點放入兩個棧中，這樣兩個鏈表的尾結(jié)點就位于兩個棧的棧頂，接下來比較下一個棧頂，直到找到最后一個相同的結(jié)點。
這種思路中，我們需要利用兩個輔助棧，空間復雜度是O(len1+len2)，時間復雜度是O(len1+len2)。和一開始的蠻力法相比，時間效率得到了提高，相當于是利用空間消耗換取時間效率。
那么，有沒有更好的方法呢？接下來要講。
方法2：判斷兩個鏈表相交的第一個結(jié)點：用到快慢指針，推薦（更優(yōu)解）
我們在上面的方法2中，之所以用到棧，是因為我們想同時遍歷到達兩個鏈表的尾結(jié)點。其實為解決這個問題我們還有一個更簡單的辦法：首先遍歷兩個鏈表得到它們的長度。在第二次遍歷的時候，在較長的鏈表上走 |len1-len2| 步，接著再同時在兩個鏈表上遍歷，找到的第一個相同的結(jié)點就是它們的第一個交點。
這種思路的時間復雜度也是O(len1+len2)，但是我們不再需要輔助棧，因此提高了空間效率。當面試官肯定了我們的最后一種思路的時候，就可以動手寫代碼了。
核心代碼：
//方法：求兩個單鏈表相交的第一個交點
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; //兩個鏈表長度的差值
Node longHead;
Node shortHead;
//找出較長的那個鏈表
if (length1 > length2) {
longHead = head1;
shortHead = head2;
lengthDif = length1 - length2;
} else {
longHead = head2;
shortHead = head1;
lengthDif = length2 - length1;
}
//將較長的那個鏈表的指針向前走length個距離
for (int i = 0; i < lengthDif; i++) {
longHead = longHead.next;
}
//將兩個鏈表的指針同時向前移動
while (longHead != null && shortHead != null) {
if (longHead == shortHead) { //第一個相同的結(jié)點就是相交的第一個結(jié)點
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)典面試題目，希望可以幫助大家順利通過面試。
相關(guān)文章
這篇文章主要介紹了java隊列之queue用法實例分析，Queue 隊列就是一個先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，Queue接口繼承Collection接口。感興趣的可以了解一下2020-07-07
Springboot使用thymeleaf動態(tài)模板實現(xiàn)刷新
這篇文章主要介紹了Springboot使用thymeleaf動態(tài)模板實現(xiàn)刷新,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
Intellj Idea中的maven工程Java文件顏色不對,未被識別的解決
這篇文章主要介紹了Intellj Idea中的maven工程Java文件顏色不對,未被識別的解決，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
數(shù)組對于每一門編程語言來說都是重要的數(shù)據(jù)結(jié)構(gòu)之一，當然不同語言對數(shù)組的實現(xiàn)及處理也不盡相同。Java?語言中提供的數(shù)組是用來存儲固定大小的同類型元素2022-04-04
這篇文章主要介紹了java語言中封裝類，涉及相關(guān)代碼示例及結(jié)果分析，以及封裝的好處簡單介紹，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
這篇文章主要為大家介紹了java全角與半角標點符號相互轉(zhuǎn)換詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
SpringBoot如何讀取war包jar包和Resource資源
這篇文章主要介紹了SpringBoot如何讀取war包jar包和Resource資源,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-01-01
Spring中使用JSR303請求約束判空的實現(xiàn)
這篇文章主要介紹了Spring中使用JSR303請求約束判空的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
這篇文章主要介紹了jstack和線程dump實例解析，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
詳解java數(shù)組進行翻轉(zhuǎn)的方法有哪些
這篇文章主要介紹了詳解java數(shù)組進行翻轉(zhuǎn)的方法有哪些,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01