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。