JAVA實現鏈表面試題講解

本文是本站小編搜索整理的關於JAVA實現鏈表面試題講解，特別適合參加Java面試的朋友閲讀，希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!

本文包含鏈表的以下內容：

1、單鏈表的創建和遍歷

2、求單鏈表中節點的個數

3、查找單鏈表中的倒數第k個結點（劍指offer，題15）

4、查找單鏈表中的中間結點

5、合併兩個有序的單鏈表，合併之後的鏈表依然有序【出現頻率高】（劍指offer，題17）

6、單鏈表的反轉【出現頻率最高】（劍指offer，題16）

7、從尾到頭打印單鏈表（劍指offer，題5）

8、判斷單鏈表是否有環

9、取出有環鏈表中，環的長度

10、單鏈表中，取出環的起始點（劍指offer，題56）。本題需利用上面的第8題和第9題。

11、判斷兩個單鏈表相交的第一個交點（劍指offer，題37）

　　1、單鏈表的創建和遍歷：

public class LinkList {

public Node head;

public Node current;

//方法：向鏈表中添加數據

public void add(int data) {

//判斷鏈表為空的時候

if (head == null) {//如果頭結點為空，説明這個鏈表還沒有創建，那就把新的結點賦給頭結點

head = new Node(data);

current = head;

} else {

//創建新的結點，放在當前節點的後面（把新的結點合鏈表進行關聯）

= new Node(data);

//把鏈表的當前索引向後移動一位

current = ; //此步操作完成之後，current結點指向新添加的那個結點

}

}

//方法：遍歷鏈表（打印輸出鏈表。方法的參數表示從節點node開始進行遍歷

public void print(Node node) {

if (node == null) {

return;

}

current = node;

while (current != null) {

tln();

current = ;

}

}

class Node {

//注：此處的兩個成員變量權限不能為private，因為private的權限是僅對本類訪問。

int data; //數據域

Node next;//指針域

public Node(int data) {

= data;

}

}

public static void main(String[] args) {

LinkList list = new LinkList();

//向LinkList中添加數據

for (int i = 0; i < 10; i++) {

(i);

}

t();// 從head節點開始遍歷輸出

}

}

上方代碼中，這裏面的Node節點採用的是內部類來表示（33行）。使用內部類的最大好處是可以和外部類進行私有操作的互相訪問。

注：內部類訪問的特點是：內部類可以直接訪問外部類的成員，包括私有；外部類要訪問內部類的成員，必須先創建對象。

為了方便添加和遍歷的操作，在LinkList類中添加一個成員變量current，用來表示當前節點的索引（03行）。

這裏面的遍歷鏈表的方法（20行）中，參數node表示從node節點開始遍歷，不一定要從head節點遍歷。

　　2、求單鏈表中節點的個數：

注意檢查鏈表是否為空。時間複雜度為O（n）。這個比較簡單。

核心代碼：

//方法：獲取單鏈表的長度

public int getLength(Node head) {

if (head == null) {

return 0;

}

int length = 0;

Node current = head;

while (current != null) {

length++;

current = ;

}

return length;

}

　　3、查找單鏈表中的倒數第k個結點：

　　3.1 普通思路：

先將整個鏈表從頭到尾遍歷一次，計算出鏈表的長度size，得到鏈表的長度之後，就好辦了，直接輸出第(size-k)個節點就可以了（注意鏈表為空，k為0，k為1，k大於鏈表中節點個數時的情況

）。時間複雜度為O（n），大概思路如下：

public int findLastNode(int index) { //index代表的是倒數第index的那個結點

//第一次遍歷，得到鏈表的長度size

if (head == null) {

return -1;

}

current = head;

while (current != null) {

size++;

current = ;

}

//第二次遍歷，輸出倒數第index個結點的數據

current = head;

for (int i = 0; i < size - index; i++) {

current = ;

}

return ;

}

如果面試官不允許你遍歷鏈表的長度，該怎麼做呢？接下來就是。

　　3.2 改進思路：（這種思路在其他題目中也有應用）

這裏需要聲明兩個指針：即兩個結點型的變量first和second，首先讓first和second都指向第一個結點，然後讓second結點往後挪k-1個位置，此時first和second就間隔了k-1個位置，然後整體向後移動這兩個節點，直到second節點走到最後一個結點的時候，此時first節點所指向的位置就是倒數第k個節點的位置。時間複雜度為O（n）

代碼實現：（初版）

public Node findLastNode(Node head, int index) {

if (node == null) {

return null;

}

Node first = head;

Node second = head;

//讓second結點往後挪index個位置

for (int i = 0; i < index; i++) {

second = ;

}

//讓first和second結點整體向後移動，直到second結點為Null

while (second != null) {

first = ;

second = ;

}

//當second結點為空的時候，此時first指向的結點就是我們要找的結點

return first;

}

代碼實現：（最終版）（考慮k大於鏈表中結點個數時的情況時，拋出異常）

上面的代碼中，看似已經實現了功能，其實還不夠健壯:

要注意k等於0的情況；

如果k大於鏈表中節點個數時，就會報空指針異常，所以這裏需要做一下判斷。

核心代碼如下：

public Node findLastNode(Node head, int k) {

if (k == 0 || head == null) {

return null;

}

Node first = head;

Node second = head;

//讓second結點往後挪k-1個位置

for (int i = 0; i < k - 1; i++) {

tln("i的值是" + i);

second = ;

if (second == null) { //説明k的值已經大於鏈表的長度了

//throw new NullPointerException("鏈表的長度小於" + k); //我們自己拋出異常，給用户以提示

return null;

}

}

//讓first和second結點整體向後移動，直到second走到最後一個結點

while ( != null) {

first = ;

second = ;

}

//當second結點走到最後一個節點的時候，此時first指向的結點就是我們要找的結點

return first;

}

　　4、查找單鏈表中的中間結點：

同樣，面試官不允許你算出鏈表的長度，該怎麼做呢？

思路：

和上面的第2節一樣，也是設置兩個指針first和second，只不過這裏是，兩個指針同時向前走，second指針每次走兩步，first指針每次走一步，直到second指針走到最後一個結點時，此時first指針所指的結點就是中間結點。注意鏈表為空，鏈表結點個數為1和2的情況。時間複雜度為O（n）。

代碼實現：

//方法：查找鏈表的中間結點

public Node findMidNode(Node head) {

if (head == null) {

return null;

}

Node first = head;

Node second = head;

//每次移動時，讓second結點移動兩位，first結點移動一位

while (second != null && != null) {

first = ;

second = ;

}

//直到second結點移動到null時，此時first指針指向的位置就是中間結點的位置

return first;

}

上方代碼中，當n為偶數時，得到的中間結點是第n/2 + 1個結點。比如鏈表有6個節點時，得到的是第4個節點。

　　5、合併兩個有序的單鏈表，合併之後的鏈表依然有序：

這道題經常被各公司考察。

例如：

鏈表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))

代碼實現：

//兩個參數代表的是兩個鏈表的頭結點

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; //新鏈表的頭結點

Node current; //current結點指向新鏈表

// 一開始，我們讓current結點指向head1和head2中較小的數據，得到head結點

if ( < ) {

head = head1;

current = head1;

head1 = ;

} else {

head = head2;

current = head2;

head2 = ;

}

while (head1 != null && head2 != null) {

if ( < ) {

= head1; //新鏈表中，current指針的下一個結點對應較小的那個數據

current = ; //current指針下移

head1 = ;

} else {

= head2;

current = ;

head2 = ;

}

}

//合併剩餘的元素

if (head1 != null) { //説明鏈表2遍歷完了，是空的

= head1;

}

if (head2 != null) { //説明鏈表1遍歷完了，是空的

= head2;

}

return head;

}

代碼測試：

public static void main(String[] args) {

LinkList list1 = new LinkList();

LinkList list2 = new LinkList();

//向LinkList中添加數據

for (int i = 0; i < 4; i++) {

(i);

}

for (int i = 3; i < 8; i++) {

(i);

}

LinkList list3 = new LinkList();

= eLinkList(, ); //將list1和list2合併，存放到list3中

t();// 從head節點開始遍歷輸出

}

上方代碼中用到的add方法和print方法和第1小節中是一致的。

運行效果：

注：《劍指offer》中是用遞歸解決的，感覺有點難理解。

　　6、單鏈表的反轉：【出現頻率最高】

例如鏈表：

1->2->3->4

反轉之後：

4->2->2->1

思路：

從頭到尾遍歷原鏈表，每遍歷一個結點，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個結點的情況。時間複雜度為O（n）

方法1：（遍歷）

//方法：鏈表的反轉

public Node reverseList(Node head) {

//如果鏈表為空或者只有一個節點，無需反轉，直接返回原鏈表的頭結點

if (head == null || == null) {

return head;

}

Node current = head;

Node next = null; //定義當前結點的下一個結點

Node reverseHead = null; //反轉後新鏈表的表頭

while (current != null) {

next = ; //暫時保存住當前結點的下一個結點，因為下一次要用

= reverseHead; //將current的下一個結點指向新鏈表的頭結點

reverseHead = current;

current = next; // 操作結束後，current節點後移

}

return reverseHead;

}

上方代碼中，核心代碼是第16、17行。

方法2：（遞歸）

這個方法有點難，先不講了。

　　7、從尾到頭打印單鏈表：

對於這種顛倒順序的問題，我們應該就會想到棧，後進先出。所以，這一題要麼自己使用棧，要麼讓系統使用棧，也就是遞歸。注意鏈表為空的情況。時間複雜度為O（n）

注：不要想着先將單鏈表反轉，然後遍歷輸出，這樣會破壞鏈表的結構，不建議。

方法1：（自己新建一個棧）

//方法：從尾到頭打印單鏈表

public void reversePrint(Node head) {

if (head == null) {

return;

}

Stack<Node> stack = new Stack<Node>(); //新建一個棧

Node current = head;

//將鏈表的所有結點壓棧

while (current != null) {-

(current); //將當前結點壓棧

current = ;

}

//將棧中的結點打印輸出即可

while (() > 0) {

tln(()); //出棧操作

}

}

方法2：（使用系統的棧：遞歸，代碼優雅簡潔）

public void reversePrint(Node head) {

if (head == null) {

return;

}

reversePrint();

tln();

}

總結：方法2是基於遞歸實現的，戴安看起來簡潔優雅，但有個問題：當鏈表很長的時候，就會導致方法調用的層級很深，有可能造成棧溢出。而方法1的顯式用棧，是基於循環實現的，代碼的魯棒性要更好一些。

　　8、判斷單鏈表是否有環：

這裏也是用到兩個指針，如果一個鏈表有環，那麼用一個指針去遍歷，是永遠走不到頭的'。

因此，我們用兩個指針去遍歷：first指針每次走一步，second指針每次走兩步，如果first指針和second指針相遇，説明有環。時間複雜度為O (n)。

方法：

//方法：判斷單鏈表是否有環

public boolean hasCycle(Node head) {

if (head == null) {

return false;

}

Node first = head;

Node second = head;

while (second != null) {

first = ; //first指針走一步

second = ; second指針走兩步

if (first == second) { //一旦兩個指針相遇，説明鏈表是有環的

return true;

}

}

return false;

}

完整版代碼：（包含測試部分）

這裏，我們還需要加一個重載的add(Node node)方法，在創建單向循環鏈表時要用到。

:

public class LinkList {

public Node head;

public Node current;

//方法：向鏈表中添加數據

public void add(int data) {

//判斷鏈表為空的時候

if (head == null) {//如果頭結點為空，説明這個鏈表還沒有創建，那就把新的結點賦給頭結點

head = new Node(data);

current = head;

} else {

//創建新的結點，放在當前節點的後面（把新的結點合鏈表進行關聯）

= new Node(data);

//把鏈表的當前索引向後移動一位

current = ;

}

}

//方法重載：向鏈表中添加結點

public void add(Node node) {

if (node == null) {

return;

}

if (head == null) {

head = node;

current = head;

} else {

= node;

current = ;

}

}

//方法：遍歷鏈表（打印輸出鏈表。方法的參數表示從節點node開始進行遍歷

public void print(Node node) {

if (node == null) {

return;

}

current = node;

while (current != null) {

tln();

current = ;

}

}

//方法：檢測單鏈表是否有環

public boolean hasCycle(Node head) {

if (head == null) {

return false;

}

Node first = head;

Node second = head;

while (second != null) {

first = ; //first指針走一步

second = ; //second指針走兩步

if (first == second) { //一旦兩個指針相遇，説明鏈表是有環的

return true;

}

}

return false;

}

class Node {

//注：此處的兩個成員變量權限不能為private，因為private的權限是僅對本類訪問。

int data; //數據域

Node next;//指針域

public Node(int data) {

= data;

}

}

public static void main(String[] args) {

LinkList list = new LinkList();

//向LinkList中添加數據

for (int i = 0; i < 4; i++) {

(i);

}

(); //將頭結點添加到鏈表當中，於是，單鏈表就有環了。備註：此時得到的這個環的結構，是下面的第8小節中圖1的那種結構。

tln(ycle());

}

}

檢測單鏈表是否有環的代碼是第50行。

88行：我們將頭結點繼續往鏈表中添加，此時單鏈表就環了。最終運行效果為true。

如果刪掉了88行代碼，此時單鏈表沒有環，運行效果為false。