JAVA實現(xiàn)鏈表面試題

1、JAVA實現(xiàn)鏈表面試題這篇文章主要介紹了 JAVA相關實現(xiàn)鏈表的面試題，代碼實現(xiàn)非常詳細，每一個方法講解也很到位，特別適合參加 Java面試的朋友閱讀。這份筆記整理了整整一個星期， 每一行代碼都是自己默寫完成， 并測試運行成功， 同時也回顧了一下劍指 offer 這本書中和鏈表有關的講解，希望對筆試和面試有所幫助。本文包含鏈表的以下內容：1、單鏈表的創(chuàng)建和遍歷2、求單鏈表中節(jié)點的個數3、查找單鏈表中的倒數第k 個結點（劍指offer ，題 15）4、查找單鏈表中的中間結點5、合并兩個有序的單鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率高】（劍指offer ，題17）6、單鏈表的反轉【出現(xiàn)頻率最高】（

2、劍指 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)建和遍歷：?1 public class LinkList 2 public Node head;3 public Node current;4 / 方法：向鏈表中添加數據5 public void add(int data) 6 / 判斷鏈表為空的時候7if (head = null) / 如果

3、頭結點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結點賦給頭8 結點9 head = new Node(data);10 current = head;11 else 12 / 創(chuàng)建新的結點，放在當前節(jié)點的后面（把新的結點合鏈表進行關聯(lián)）13 current.next = new Node(data);14 / 把鏈表的當前索引向后移動一位15current = current.next; /此步操作完成之后，current 結點指向新添加的那個結點16 17 18/ 方法：遍歷鏈表（打印輸出鏈表。方法的參數表示從節(jié)點node 開始進行遍歷19 public void print(Node nod

4、e) 20 if (node = null) 21 return;22 23 current = node;24 while (current != null) 25 System.out.println(current.data);26 current = current.next;27 28 29 class Node 30 / 注：此處的兩個成員變量權限不能為private ，因為 private 的權限是僅對本類訪問。31 int data; / 數據域32 Node next;/ 指針域33 public Node(int data) 34 this.data = data;35 3

5、6 37 public static void main(String args) 38 LinkList list = new LinkList();39 / 向 LinkList 中添加數據40 for (int i = 0; i < 10; i+) 41 list.add(i);42 43 list.print(list.head);/ 從 head 節(jié)點開始遍歷輸出44 45 4647484950515253上方代碼中，這里面的Node 節(jié)點采用的是內部類來表示（33 行）。使用內部類的最大好處是可以和外部類進行私有操作的互相訪問。注：內部類訪問的特點是：內部類可以直接訪問外部類

6、的成員，包括私有；外部類要訪問內部類的成員，必須先創(chuàng)建對象。為了方便添加和遍歷的操作，在LinkList 類中添加一個成員變量current ，用來表示當前節(jié)點的索引（ 03 行）。這里面的遍歷鏈表的方法（20 行）中，參數node 表示從 node 節(jié)點開始遍歷，不一定要從head 節(jié)點遍歷。2、求單鏈表中節(jié)點的個數：注意檢查鏈表是否為空。時間復雜度為O（ n）。這個比較簡單。核心代碼：?12 / 方法：獲取單鏈表的長度3 public int getLength(Node head) 4 if (head = null) 5 return 0;6 7 int length = 0;8 No

7、de current = head;9 while (current != null) 10 length+;11 current = current.next;12 13 return length;14 153、查找單鏈表中的倒數第3.1 普通思路：k 個結點：先將整個鏈表從頭到尾遍歷一次，計算出鏈表的長度size，得到鏈表的長度之后，就好辦了，直接輸出第 (size-k)個節(jié)點就可以了（注意鏈表為空， k 為 0， k 為 1， k 大于鏈表中節(jié)點個數時的情況）。時間復雜度為O（ n），大概思路如下：?12index 的那個結點public int findLastNode(int in

8、dex) /index 代表的是倒數第3/ 第一次遍歷，得到鏈表的長度size4if (head = null) 5return -1;67current = head;8while (current != null) 9size+;10current = current.next;1112index 個結點的數據/ 第二次遍歷，輸出倒數第13current = head;14for (int i = 0; i < size - index; i+) 15current = current.next;1617return current.data;18192021如果面試官不允許你遍歷鏈

9、表的長度，該怎么做呢？接下來就是。3.2 改進思路：（這種思路在其他題目中也有應用）這里需要聲明兩個指針：即兩個結點型的變量first 和 second，首先讓 first 和 second 都指向第一個結點，然后讓 second 結點往后挪k-1 個位置，此時first 和 second 就間隔了 k-1 個位置，然后整體向后移動這兩個節(jié)點，直到second 節(jié)點走到最后一個結點的時候，此時first節(jié)點所指向的位置就是倒數第k 個節(jié)點的位置。時間復雜度為O（ n）代碼實現(xiàn)：（初版）?123public Node findLastNode(Node head, int index) 4if

10、(node = null) 5return null;67Node first = head;8Node second = head;9/ 讓 second 結點往后挪 index 個位置10for (int i = 0; i < index; i+) 11second = second.next;1213second 結點為 Null/ 讓 first 和 second 結點整體向后移動，直到14while (second != null) 15first = first.next;16second = second.next;1718first 指向的結點就是我們要找的結點/ 當 s

11、econd 結點為空的時候，此時19return first;20212223代碼實現(xiàn)：（最終版）（考慮 k 大于鏈表中結點個數時的情況時，拋出異常）上面的代碼中，看似已經實現(xiàn)了功能，其實還不夠健壯:要注意 k 等于 0 的情況；如果 k 大于鏈表中節(jié)點個數時，就會報空指針異常，所以這里需要做一下判斷。核心代碼如下：?1 public Node findLastNode(Node head, int k) 2 if (k = 0 | head = null) 3 return null;4 5 Node first = head;6Node second = head;7/ 讓 second

12、結點往后挪 k-1 個位置8 for (int i = 0; i < k - 1; i+) 9 System.out.println("i 的值是 " + i);10 second = second.next;11 if (second = null) / 說明 k 的值已經大于鏈表的長度了12 /throw new NullPointerException(" 鏈表的長度小于 " + k); / 我們自己拋出異常，給用戶13 以提示14 return null;15 16 17/ 讓 first 和 second 結點整體向后移動，直到secon

13、d 走到最后一個結點18 while (second.next != null) 19 first = first.next;20 second = second.next;21 22/ 當 second 結點走到最后一個節(jié)點的時候，此時first 指向的結點就是我們要找的結點23 return first;24 25264、查找單鏈表中的中間結點：同樣，面試官不允許你算出鏈表的長度，該怎么做呢？思路：和上面的第2 節(jié)一樣，也是設置兩個指針first 和 second，只不過這里是，兩個指針同時向前走， second 指針每次走兩步，first 指針每次走一步，直到second 指針走到最后一

14、個結點時，此時first 指針所指的結點就是中間結點。注意鏈表為空，鏈表結點個數為1 和 2 的情況。時間復雜度為O（ n）。代碼實現(xiàn)：?1 / 方法：查找鏈表的中間結點2 public Node findMidNode(Node head) 3 if (head = null) 4 return null;5 6 Node first = head;7 Node second = head;8/ 每次移動時，讓second 結點移動兩位，first 結點移動一位9 while (second != null && second.next != null) 10 first =

15、 first.next;11 second = second.next.next;12 13 / 直到 second 結點移動到 null 時，此時 first 指針指向的位置就是中間結點的位置14 return first;15 161718上方代碼中，當n 為偶數時，得到的中間結點是第n/2 + 1 個結點。比如鏈表有6 個節(jié)點時，得到的是第4 個節(jié)點。5、合并兩個有序的單鏈表，合并之后的鏈表依然有序：這道題經常被各公司考察。例如：鏈表 1：1->2->3->4鏈表 2：2->3->4->5合并后：1->2->2->3->3-&g

16、t;4->4->5解題思路：挨著比較鏈表1 和鏈表 2。這個類似于歸并排序。尤其要注意兩個鏈表都為空、和其中一個為空的情況。只需要O(1) 的空間。時間復雜度為O (max(len1,len2)代碼實現(xiàn)：?1 / 兩個參數代表的是兩個鏈表的頭結點2 public Node mergeLinkList(Node head1, Node head2) 3 if (head1 = null && head2 = null) / 如果兩個鏈表都為空4 return null;5 6 if (head1 = null) 7 return head2;8 9 if (head2

17、 = null) 10 return head1;11 12 Node head; / 新鏈表的頭結點13Node current; /current 結點指向新鏈表14/ 一開始，我們讓 current 結點指向 head1 和 head2 中較小的數據，得到head 結點15 if (head1.data < head2.data) 16 head = head1;17 current = head1;18 head1 = head1.next;19 else 20 head = head2;21 current = head2;22 head2 = head2.next;23 24

18、 while (head1 != null && head2 != null) 25 if (head1.data < head2.data) 26 current.next = head1; / 新鏈表中， current 指針的下一個結點對應較小的那個數據27current = current.next; /current指針下移28 head1 = head1.next;29 else 30 current.next = head2;31 current = current.next;32 head2 = head2.next;33 34 35 / 合并剩余的元素3

19、6 if (head1 != null) / 說明鏈表 2 遍歷完了，是空的37 current.next = head1;38 39 if (head2 != null) / 說明鏈表 1 遍歷完了，是空的40 current.next = head2;41 42 return head;43 444546474849代碼測試：?1 public static void main(String args) 2 LinkList list1 = new LinkList();3 LinkList list2 = new LinkList();4 / 向 LinkList 中添加數據5 for

20、(int i = 0; i < 4; i+) 6 list1.add(i);7 8 for (int i = 3; i < 8; i+) 9 list2.add(i);10 11 LinkList list3 = new LinkList();12list3.head = list3.mergeLinkList(list1.head, list2.head); /將 list1 和 list2 合并，存放到list313 中14 list3.print(list3.head);/ 從 head 節(jié)點開始遍歷輸出15 1617上方代碼中用到的add 方法和 print 方法和第1 小

21、節(jié)中是一致的。運行效果：注：劍指 offer 中是用遞歸解決的，感覺有點難理解。6、單鏈表的反轉： 【出現(xiàn)頻率最高】例如鏈表：1->2->3->4反轉之后：4->2->2->1思路：從頭到尾遍歷原鏈表，每遍歷一個結點，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個結點的情況。時間復雜度為O（ n）方法 1：（遍歷）?1 / 方法：鏈表的反轉2 public Node reverseList(Node head) 3 / 如果鏈表為空或者只有一個節(jié)點，無需反轉，直接返回原鏈表的頭結點4 if (head = null | head.next = null)

22、 5 return head;6 7 Node current = head;8 Node next = null; / 定義當前結點的下一個結點9 Node reverseHead = null; / 反轉后新鏈表的表頭10 while (current != null) 11 next = current.next; / 暫時保存住當前結點的下一個結點，因為下一次要用12 current.next = reverseHead; / 將 current 的下一個結點指向新鏈表的頭結點13 reverseHead = current;14 current = next; / 操作結束后， cu

23、rrent 節(jié)點后移15 16 return reverseHead;17 181920212223上方代碼中，核心代碼是第16、17 行。方法 2：（遞歸）這個方法有點難，先不講了。7、從尾到頭打印單鏈表：對于這種顛倒順序的問題，我們應該就會想到棧，后進先出。所以， 這一題要么自己使用棧，要么讓系統(tǒng)使用棧，也就是遞歸。注意鏈表為空的情況。時間復雜度為O（ n）注：不要想著先將單鏈表反轉，然后遍歷輸出，這樣會破壞鏈表的結構，不建議。方法 1：（自己新建一個棧）?123 / 方法：從尾到頭打印單鏈表4 public void reversePrint(Node head) 5 if (head

24、= null) 6 return;7 8 Stack<Node> stack = new Stack<Node>(); / 新建一個棧9 Node current = head;10 / 將鏈表的所有結點壓棧11 while (current != null) -12 stack.push(current); / 將當前結點壓棧13 current = current.next;14 15 / 將棧中的結點打印輸出即可16 while (stack.size() > 0) 17 System.out.println(stack.pop().data); / 出棧操

25、作18 19 2021方法 2：（使用系統(tǒng)的棧：遞歸，代碼優(yōu)雅簡潔）?1public void reversePrint(Node head) 2 if (head = null) 3 return;4 5 reversePrint(head.next);6 System.out.println(head.data);7 89總結：方法2 是基于遞歸實現(xiàn)的，戴安看起來簡潔優(yōu)雅，但有個問題：當鏈表很長的時候，就會導致方法調用的層級很深，有可能造成棧溢出。而方法 1 的顯式用棧， 是基于循環(huán)實現(xiàn)的，代碼的魯棒性要更好一些。8、判斷單鏈表是否有環(huán)：這里也是用到兩個指針，如果一個鏈表有環(huán)，那么用一個指

26、針去遍歷，是永遠走不到頭的。因此，我們用兩個指針去遍歷：first 指針每次走一步， second 指針每次走兩步， 如果 first指針和 second 指針相遇，說明有環(huán)。時間復雜度為O (n)。方法：?123/ 方法：判斷單鏈表是否有環(huán)4public boolean hasCycle(Node head) 5if (head = null) 6return false;78Node first = head;9Node second = head;10while (second != null) 11first = first.next; /first指針走一步12second = se

27、cond.next.next; second 指針走兩步13if (first = second) / 一旦兩個指針相遇，說明鏈表是有環(huán)的14return true;151617return false;18192021完整版代碼：（包含測試部分）這里，我們還需要加一個重載的add(Node node) 方法，在創(chuàng)建單向循環(huán)鏈表時要用到。?1LinkList.java:2 public class LinkList 3 public Node head;4 public Node current;5 / 方法：向鏈表中添加數據6 public void add(int data) 7 / 判斷

28、鏈表為空的時候8if (head = null) / 如果頭結點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結點賦給頭9 結點10 head = new Node(data);11 current = head;12 else 13 / 創(chuàng)建新的結點，放在當前節(jié)點的后面（把新的結點合鏈表進行關聯(lián)）14 current.next = new Node(data);15 / 把鏈表的當前索引向后移動一位16 current = current.next;17 18 19 / 方法重載：向鏈表中添加結點20 public void add(Node node) 21 if (node = null) 2

29、2 return;23 24 if (head = null) 25 head = node;26 current = head;27 else 28 current.next = node;29 current = current.next;30 31 32/ 方法：遍歷鏈表（打印輸出鏈表。方法的參數表示從節(jié)點node 開始進行遍歷33 public void print(Node node) 34 if (node = null) 35 return;36 37 current = node;38 while (current != null) 39 System.out.println(

30、current.data);40 current = current.next;41 42 43 / 方法：檢測單鏈表是否有環(huán)44 public boolean hasCycle(Node head) 45 if (head = null) 46 return false;47 48 Node first = head;49 Node second = head;50 while (second != null) 51first = first.next; /first指針走一步52 second = second.next.next; /second 指針走兩步53 if (first =

31、second) / 一旦兩個指針相遇，說明鏈表是有環(huán)的54 return true;55 56 57 return false;58 59 class Node 60 / 注：此處的兩個成員變量權限不能為private ，因為 private 的權限是僅對本類訪問。61 int data; / 數據域62 Node next;/ 指針域63 public Node(int data) 64 this.data = data;65 66 67 public static void main(String args) 68 LinkList list = new LinkList();69 / 向

32、 LinkList 中添加數據70 for (int i = 0; i < 4; i+) 71 list.add(i);72 73 list.add(list.head); / 將頭結點添加到鏈表當中，于是，單鏈表就有環(huán)了。備注：此時得74到的這個環(huán)的結構，是下面的第8 小節(jié)中圖1 的那種結構。75 System.out.println(list.hasCycle(list.head);76 77 787980818283848586878889檢測單鏈表是否有環(huán)的代碼是第50 行。88 行：我們將頭結點繼續(xù)往鏈表中添加，此時單鏈表就環(huán)了。最終運行效果為如果刪掉了 88 行代碼，此時單鏈

33、表沒有環(huán)，運行效果為 false。true 。9、取出有環(huán)鏈表中，環(huán)的長度：我們平時碰到的有環(huán)鏈表是下面的這種：（圖1）上圖中環(huán)的長度是4。但有可能也是下面的這種：（圖 2）此時，上圖中環(huán)的長度就是那怎么求出環(huán)的長度呢？思路：3 了。這里面，我們需要先利用上面的第 7 小節(jié)中的 hasCycle方法（判斷鏈表是否有環(huán)的那個方法） ，這個方法的返回值是 boolean 型，但是現(xiàn)在要把這個方法稍做修改， 讓其返回值為相遇的那個結點。然后， 我們拿到這個相遇的結點就好辦了，這個結點肯定是在環(huán)里嘛，我們可以讓這個結點對應的指針一直往下走，直到它回到原點，就可以算出環(huán)的長度了。方法：?1 / 方法：判

34、斷單鏈表是否有環(huán)。返回的結點是相遇的那個結點2 public Node hasCycle(Node head) 3 if (head = null) 4 return null;5 6 Node first = head;7 Node second = head;8 while (second != null) 9 first = first.next;10 second = second.next.next;11 if (first = second) / 一旦兩個指針相遇，說明鏈表是有環(huán)的12 return first; / 將相遇的那個結點進行返回13 14 15 return null

35、;16 17/ 方法：有環(huán)鏈表中，獲取環(huán)的長度。參數node 代表的是相遇的那個結點18 public int getCycleLength(Node node) 19 if (head = null) 20 return 0;21 22 Node current = node;23 int length = 0;24 while (current != null) 25 current = current.next;26 length+;27 if (current = node) / 當 current 結點走到原點的時候28 return length;29 30 31 return l

36、ength;32 3334353637383940完整版代碼：（包含測試部分）?1 public class LinkList 2 public Node head;3 public Node current;4 public int size;5 / 方法：向鏈表中添加數據6 public void add(int data) 7 / 判斷鏈表為空的時候8if (head = null) / 如果頭結點為空，說明這個鏈表還沒有創(chuàng)建，那就把新的結點賦給頭9 結點10 head = new Node(data);11 current = head;12 else 13 / 創(chuàng)建新的結點，放在當前

37、節(jié)點的后面（把新的結點合鏈表進行關聯(lián)）14 current.next = new Node(data);15 / 把鏈表的當前索引向后移動一位16current = current.next; /此步操作完成之后，current 結點指向新添加的那個結點17 18 19 / 方法重載：向鏈表中添加結點20 public void add(Node node) 21 if (node = null) 22 return;23 24 if (head = null) 25 head = node;26 current = head;27 else 28 current.next = node;29

38、 current = current.next;30 31 32/ 方法：遍歷鏈表（打印輸出鏈表。方法的參數表示從節(jié)點node 開始進行遍歷33 public void print(Node node) 34 if (node = null) 35 return;36 37 current = node;38 while (current != null) 39 System.out.println(current.data);40 current = current.next;41 42 43 / 方法：判斷單鏈表是否有環(huán)。返回的結點是相遇的那個結點44 public Node hasCyc

39、le(Node head) 45 if (head = null) 46 return null;47 48 Node first = head;49 Node second = head;50 while (second != null) 51 first = first.next;52 second = second.next.next;53 if (first = second) / 一旦兩個指針相遇，說明鏈表是有環(huán)的54 return first; / 將相遇的那個結點進行返回55 56 57 return null;58 59/ 方法：有環(huán)鏈表中，獲取環(huán)的長度。參數node 代表的是

40、相遇的那個結點60 public int getCycleLength(Node node) 61 if (head = null) 62 return 0;63 64 Node current = node;65 int length = 0;66 while (current != null) 67 current = current.next;68 length+;69 if (current = node) / 當 current 結點走到原點的時候70 return length;71 72 73 return length;74 75 class Node 76 / 注：此處的兩個

41、成員變量權限不能為private ，因為 private 的權限是僅對本類訪問。77 int data; / 數據域78 Node next;/ 指針域79 public Node(int data) 80 this.data = data;81 82 83 public static void main(String args) 84 LinkList list1 = new LinkList();85 Node second = null; / 把第二個結點記下來86 / 向 LinkList 中添加數據87 for (int i = 0; i < 4; i+) 88 list1.a

42、dd(i);89 if (i = 1) 90 second = list1.current; / 把第二個結點記下來91 92 93 list1.add(second); / 將尾結點指向鏈表的第二個結點，于是單鏈表就有環(huán)了，備注：此94時得到的環(huán)的結構，是本節(jié)中圖2 的那種結構95 Node current = list1.hasCycle(list1.head); / 獲取相遇的那個結點96 System.out.println(" 環(huán)的長度為 " + list1.getCycleLength(current);97 98 99運行效果：如果將上面的 104 至 122

43、 行的測試代碼改成下面這樣的： （即：將圖 2 中的結構改成圖 1 中的結構）?12 public static void main(String args) 3 LinkList list1 = new LinkList();4 / 向 LinkList 中添加數據5 for (int i = 0; i < 4; i+) 6 list1.add(i);7 8list1.add(list1.head); / 將頭結點添加到鏈表當中 （將尾結點指向頭結點） ，于是，單鏈表9就有環(huán)了。備注：此時得到的這個環(huán)的結構，是本節(jié)中圖1 的那種結構。10 Node current = list1.ha

44、sCycle(list1.head);11 System.out.println(" 環(huán)的長度為 " + list1.getCycleLength(current);12 13運行結果：如果把上面的代碼中的第8 行刪掉，那么這個鏈表就沒有環(huán)了，于是運行的結果為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

45、 之后，需要用到兩個指針變量first 和 second，先讓 second 指針走 length 步；然后讓 first 指針和 second 指針同時各走一步， 當兩個指針相遇時，相遇時的結點就是環(huán)的起始點。注：為了找到環(huán)的起始點，我們需要先獲取環(huán)的長度，而為了獲取環(huán)的長度，我們需要先判斷是否有環(huán)。所以這里面其實是用到了三個方法。代碼實現(xiàn)：方法 1 的核心代碼：?1/ 方法：獲取環(huán)的起始點。參數length 表示環(huán)的長度2 public Node getCycleStart(Node head, int cycleLength) 3 if (head = null) 4 return null;5 6 Node first = head;7 Node second = head;8 / 先讓 second 指針走 length 步9 for (int i = 0; i < cycleLength; i+) 10 second = secon