數(shù)據(jù)結(jié)構(gòu) - 鏈表 - 面試中常見的鏈表算法題

數(shù)據(jù)結(jié)構(gòu)是面試中必定考查的知識(shí)點(diǎn)，面試者需要掌握幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)：線性表（數(shù)組、鏈表）、棧與隊(duì)列、樹（二叉樹、二叉查找樹、平衡二叉樹、紅黑樹）、圖。

本文主要介紹線性表中的常見的鏈表數(shù)據(jù)結(jié)構(gòu)。包括

• 概念簡介
• 鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)（Java）
• 常見的鏈表算法題（Java）。

---

概念簡介

如果對鏈表概念已經(jīng)基本掌握，可以跳過該部分，直接查看常見鏈表算法題。

線性表基本概念

鏈表是一種線性表，因此我們首先了解一下什么是線性表：

線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，它是n個(gè)數(shù)據(jù)元素的有限序列。實(shí)現(xiàn)線性表的方式一般有兩種：

• 使用數(shù)組存儲(chǔ)線性表的元素，即用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
• 使用鏈表存儲(chǔ)線性表的元素，即用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。

鏈表基本概念

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

相比于線性表順序結(jié)構(gòu)（數(shù)組），操作復(fù)雜。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。
鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。

鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。

數(shù)組和鏈表的區(qū)別

• 數(shù)組是同類型的連續(xù)的一個(gè)存儲(chǔ)空間，鏈表是不連續(xù)的，其元素結(jié)點(diǎn)是一個(gè)結(jié)構(gòu)體。
• 數(shù)組是在棧中分配的，即數(shù)組大小在編譯時(shí)就已經(jīng)確定，即內(nèi)存是靜態(tài)分配的；鏈表是在堆中分配的，運(yùn)行過程才具體分配，即鏈表是動(dòng)態(tài)分配內(nèi)存。
• 數(shù)組對于元素的查詢是通過下標(biāo)直接索引，而鏈表是通過結(jié)點(diǎn)之間的鏈接一步一步進(jìn)行遍歷。數(shù)組對元素的查詢時(shí)間復(fù)雜度是O(1)，鏈表對元素的查詢時(shí)間復(fù)雜度是O(n).
• 數(shù)組對于元素的插入、刪除效率較低，需要進(jìn)行挪位。而鏈表插入，刪除只需要操作相應(yīng)位置上的指針即可。數(shù)組對元素的插入、刪除時(shí)間復(fù)雜度是O(n)，鏈表對元素的插入、刪除時(shí)間復(fù)雜度是O(1)。

---

鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

鏈表由一系列結(jié)點(diǎn)組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

定義節(jié)點(diǎn)為類：ListNode。具體實(shí)現(xiàn)如下：

public class ListNode {public int val; // 數(shù)據(jù)域public ListNode next; // 指針域public ListNode() {}public ListNode(int val) {this.val = val;}// 打印鏈表節(jié)點(diǎn)元素值public static void printList(ListNode head) {while (head != null) {System.out.print(head.val + "->");head = head.next;}System.out.println("null");}}

---

常見的鏈表算法題（單鏈表）

1. 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)

/*** 1. 求單鏈表中節(jié)點(diǎn)的個(gè)數(shù)：* 注意檢查鏈表是否為空。時(shí)間復(fù)雜度為O（n）。這個(gè)比較簡單。* @param head 鏈表頭結(jié)點(diǎn)* @return 鏈表中節(jié)點(diǎn)的個(gè)數(shù)*/ public static int getLength(ListNode head) {if (head == null) {return 0;}int length = 0;ListNode current = head;while (current != null) { // 當(dāng)前元素不為空length++;current = current.next;}return length; }

2. 查找單鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)（劍指offer，題15）

思路：這里需要聲明兩個(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è)位置，然后整體向后移動(dòng)這兩個(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）。

/*** 2. 查找單鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)（劍指offer，題15）* 時(shí)間復(fù)雜度為O（n）** 考慮k=0和k大于鏈表長度的情況* @param head 鏈表頭結(jié)點(diǎn)* @param k 倒數(shù)第k* @return 倒數(shù)第k個(gè)節(jié)點(diǎn)*/ public static ListNode findLastNode(ListNode head, int k){if (head == null || k <= 0) { // 輸入異常throw new RuntimeException("輸入?yún)?shù)格式不對...");}ListNode first = head; // 兩個(gè)指針ListNode second = head;for (int i = 0; i < k - 1; i++) {second = second.next;if (second == null) { // 說明k的值大于鏈表的長度throw new RuntimeException("k越界");}}// 兩個(gè)指針同時(shí)移動(dòng)，second到達(dá)尾節(jié)點(diǎn)時(shí)，first是倒數(shù)第k個(gè)節(jié)點(diǎn)while (second.next != null) {first = first.next;second = second.next;}return first; }

3. 查找單鏈表中的中間結(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）。

/*** 3. 查找單鏈表中的中間結(jié)點(diǎn)：* 上方代碼中，當(dāng)n為偶數(shù)時(shí)，得到的中間結(jié)點(diǎn)是第n/2個(gè)結(jié)點(diǎn)。比如鏈表有6個(gè)節(jié)點(diǎn)時(shí)，得到的是第3個(gè)節(jié)點(diǎn)。* @param head 鏈表頭結(jié)點(diǎn)* @return 中間節(jié)點(diǎn)*/ public static ListNode findMidNode(ListNode head){if (head == null || head.next == null || head.next.next == null) {return null;}ListNode first = head;ListNode second = head;while (second.next != null && second.next.next != null) {first = first.next;second = second.next.next;}return first; }

4. 合并兩個(gè)有序的單鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率高】（劍指offer，題17）

這道題經(jīng)常被各公司考察。例如：

鏈表1：1->2->3->4； 鏈表2：2->3->4->5； 合并后：1->2->2->3->3->4->4->5

解題思路：挨個(gè)比較鏈表1和鏈表2。這個(gè)類似于歸并排序。
尤其要注意兩個(gè)鏈表都為空、和其中一個(gè)為空的情況。
只需要O(1)的空間。時(shí)間復(fù)雜度為O (max(len1,len2))。

/*** 4. 合并兩個(gè)有序的單鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率高】（劍指offer，題17）* 解題思路：挨著比較鏈表1和鏈表2。這個(gè)類似于歸并排序。尤其要注意兩個(gè)鏈表都為空、和其中一個(gè)為空的情況。* 只需要O(1)的空間。時(shí)間復(fù)雜度為O (max(len1,len2))* @param head1 鏈表1頭結(jié)點(diǎn)* @param head2 鏈表2頭結(jié)點(diǎn)* @return 合并后的鏈表頭結(jié)點(diǎn)*/ public static ListNode mergeLinkList(ListNode head1, ListNode head2) {// 第一個(gè)鏈表為空if (head1 == null) {return head2;}// 第二個(gè)鏈表為空if (head2 == null) {return head1;}// 設(shè)置鏈表頭結(jié)點(diǎn)ListNode head = new ListNode(-1);ListNode temp = head;while (head1 != null && head2 != null) {if (head1.val < head2.val) { // 鏈表1的元素小于鏈表2的元素temp.next = head1;head1 = head1.next;} else {temp.next = head2;head2 = head2.next;}temp = temp.next;}// 鏈表1沒有遍歷結(jié)束if (head1 != null) {temp.next = head1;}// 鏈表2沒有遍歷結(jié)束if (head2 != null) {temp.next = head2;}return head.next; // 返回空節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) }

5. 單鏈表的反轉(zhuǎn)：【出現(xiàn)頻率最高】（不使用額外的空間）

例如：

鏈表：1->2->3->4 反轉(zhuǎn)之后：4->3->2->1

思路：從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。
注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。時(shí)間復(fù)雜度為O（n）。

/*** 5. 單鏈表的反轉(zhuǎn)：【出現(xiàn)頻率最高】（不使用額外的空間）* 例如鏈表：1->2->3->4 反轉(zhuǎn)之后：4->3->2->1* 思路：從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。* 注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。時(shí)間復(fù)雜度為O（n）* @param head 鏈表頭結(jié)點(diǎn)* @return 鏈表反轉(zhuǎn)后的頭結(jié)點(diǎn)*/ public static ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = null; // 保存鏈表新表頭ListNode current = head; // 保存當(dāng)前鏈表的遍歷節(jié)點(diǎn)while (current != null) {ListNode next = current.next; // 保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)current.next = newHead;newHead = current;current = next;}return newHead; }

6. 從尾到頭打印單鏈表

遞歸實(shí)現(xiàn)：用遞歸實(shí)現(xiàn)，但有個(gè)問題：當(dāng)鏈表很長的時(shí)候，就會(huì)導(dǎo)致方法調(diào)用的層級很深，有可能造成棧溢出。

/** * 6.從尾到頭打印單鏈表 * 用遞歸實(shí)現(xiàn)，但有個(gè)問題：當(dāng)鏈表很長的時(shí)候，就會(huì)導(dǎo)致方法調(diào)用的層級很深，有可能造成棧溢出。 * 注意鏈表為空的情況。時(shí)間復(fù)雜度為O（n） * @param head 鏈表頭結(jié)點(diǎn) */ public static void reversePrint(ListNode head) {if (head == null) {return;}reversePrint(head.next);System.out.print(head.val + "->"); }

非遞歸實(shí)現(xiàn)：對于這種顛倒順序的問題，我們應(yīng)該就會(huì)想到棧，后進(jìn)先出。顯式用棧，是基于循環(huán)實(shí)現(xiàn)的，代碼的魯棒性要更好一些。
注意鏈表為空的情況。時(shí)間復(fù)雜度為O（n）。

/*** 6. 從尾到頭打印單鏈表* 對于這種顛倒順序的問題，我們應(yīng)該就會(huì)想到棧，后進(jìn)先出。* 顯式用棧，是基于循環(huán)實(shí)現(xiàn)的，代碼的魯棒性要更好一些。* 注意鏈表為空的情況。時(shí)間復(fù)雜度為O（n）* @param head 鏈表頭結(jié)點(diǎn)*/ public static void reversePrintByStack(ListNode head) {if (head == null) {return;}Stack<ListNode> stack = new Stack<>();while (head != null) { // 將鏈表元素壓入棧中stack.add(head);head = head.next;}while (!stack.isEmpty()) { // 將鏈表元素出棧打印System.out.print(stack.pop().val + "->");} }

7. 判斷單鏈表是否有環(huán)

這里也是用到兩個(gè)指針，如果一個(gè)鏈表有環(huán)，那么用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的。因此，我們用兩個(gè)指針去遍歷：first指針每次走一步，second指針每次走兩步，如果first指針和second指針相遇，說明有環(huán)。
時(shí)間復(fù)雜度為O (n)。

/*** 7. 判斷單鏈表是否有環(huán)：* 這里也是用到兩個(gè)指針，如果一個(gè)鏈表有環(huán)，那么用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的。* 因此，我們用兩個(gè)指針去遍歷：first指針每次走一步，second指針每次走兩步，* 如果first指針和second指針相遇，說明有環(huán)。時(shí)間復(fù)雜度為O (n)。* @param head 鏈表頭結(jié)點(diǎn)* @return 是否存在環(huán)*/ public static boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode first = head; // 每次移動(dòng)一步ListNode second = head; // 每次移動(dòng)兩步while (second != null && second.next != null) { // 判斷空指針first = first.next;second = second.next.next;if (first == second) {return true;}}return false; }

8. 取出有環(huán)鏈表中環(huán)的長度

思路：環(huán)的長度即為從開始到相遇處first走的步數(shù)。

/*** 8. 取出有環(huán)鏈表中，環(huán)的長度：從開始到相遇處first走的步數(shù)* @param head 鏈表頭結(jié)點(diǎn)* @return 環(huán)的長度*/ public static int getCycleLength(ListNode head){if (head == null || head.next == null) {return 0;}int length = 0; // 環(huán)的長度ListNode first = head; // 每次移動(dòng)一步ListNode second = head; // 每次移動(dòng)兩步while (second != null && second.next != null) { // 判斷空指針first = first.next;second = second.next.next;length++;if (first == second) {return length;}}return 0; }

9. 有環(huán)單鏈表中，取出環(huán)的起始點(diǎn)

思路：從相遇點(diǎn)開始，設(shè)置一個(gè)節(jié)點(diǎn)從頭開始，然后最終相遇的節(jié)點(diǎn)就是環(huán)的起始點(diǎn)。由上圖中的a=c可知。

/*** 9、單鏈表中，取出環(huán)的起始點(diǎn)：從相遇點(diǎn)開始，設(shè)置一個(gè)節(jié)點(diǎn)從頭開始，然后最終相遇的節(jié)點(diǎn)就是環(huán)的起始點(diǎn)。* @param head 鏈表頭結(jié)點(diǎn)* @return 鏈表中環(huán)的起始節(jié)點(diǎn)*/ public static ListNode getCycleStart(ListNode head) {if (head == null || head.next == null) {return null;}ListNode first = head; // 每次移動(dòng)一步ListNode second = head; // 每次移動(dòng)兩步while (second != null && second.next != null) { // 判斷空指針first = first.next;second = second.next.next;if (first == second) {ListNode temp = head;while (temp != second) {temp = temp.next;second = second.next;}return second;}}return null; }

10. 判斷兩個(gè)單鏈表相交的第一個(gè)交點(diǎn)。 劍指offer，題37。

思路：先遍歷兩個(gè)鏈表得到長度差，讓長的鏈表先走長度差步，然后再同時(shí)走相遇的第一個(gè)節(jié)點(diǎn)就是返回結(jié)果。

/*** 10、判斷兩個(gè)單鏈表相交的第一個(gè)交點(diǎn)。 劍指offer，題37。* 先遍歷兩個(gè)鏈表得到長度差，讓長的鏈表先走長度差步，然后再同時(shí)走相遇的第一個(gè)節(jié)點(diǎn)就是返回結(jié)果。* 時(shí)間復(fù)雜度為：O(m+n)* @param head1 鏈表1頭結(jié)點(diǎn)* @param head2 鏈表2頭結(jié)點(diǎn)* @return 相交的第一個(gè)節(jié)點(diǎn)*/ public static ListNode meetNode(ListNode head1, ListNode head2){if (head1 == null || head2 == null) {return null;}int len1 = 0;int len2 = 0;ListNode temp1 = head1;ListNode temp2 = head2;while (temp1 != null) {len1++;temp1 = temp1.next;}while (temp2 != null) {len2++;temp2 = temp2.next;}int diff = Math.abs(len1 - len2);ListNode longHead = head1;ListNode shortHead = head2;if (len1 < len2) {longHead = head2;shortHead = head1;}for (int i = 0; i < diff; i++) {longHead = longHead.next;}while (longHead != null && shortHead != null && longHead != shortHead) {longHead = longHead.next;shortHead = shortHead.next;}return longHead; }

11. 以 k 個(gè)節(jié)點(diǎn)為段，反轉(zhuǎn)單鏈表。

Reverse Nodes in k_Group，Leetcode上的算法題，第5題的高級變種

/*** 11、以 k 個(gè)節(jié)點(diǎn)為段，反轉(zhuǎn)單鏈表。* Reverse Nodes in k_Group，Leetcode上的算法題，第6題的高級變種* @param head 鏈表頭結(jié)點(diǎn)* @param k 每k個(gè)節(jié)點(diǎn)反轉(zhuǎn)* @return 反轉(zhuǎn)后的鏈表頭*/ public static ListNode reverseKGroup2(ListNode head, int k) {ListNode curr = null;int count = 0;while (curr != null && count != k) { // find the k+1 nodecurr = curr.next;count++;}if (count == k) { // if k+1 node is foundcurr = reverseKGroup2(curr, k); // reverse list with k+1 node as head// head - head-pointer to direct part,// curr - head-pointer to reversed part;while (count-- > 0) { // reverse current k-groupListNode tmp = head.next; // tmp - next head in direct parthead.next = curr; // preappending "direct" head to the reversed listcurr = head; // move head of reversed part to a new nodehead = tmp; // move "direct" head to the next node in direct part}head = curr;}return head; }

總結(jié)

以上是生活随笔為你收集整理的数据结构 - 链表 - 面试中常见的链表算法题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。