鏈表面試題精講_七月算法出品

1、鏈表面試題精講 七月算法 曹曹鵬鵬 2015年4月24日2/提綱n鏈表簡介n面試題總體分析n一些例題o例1 鏈表的插入與（懶）刪除o例2 鏈表翻轉(zhuǎn)o例3 單鏈表找環(huán)及起點(diǎn)和環(huán)長度o例4 兩個鏈表找交點(diǎn)o例5 復(fù)制帶有隨機(jī)指針的鏈表o例6 鏈表partition過程n總結(jié)鏈表簡介o 鏈表 ：一個元素和下一個元素靠指針連接（松散），不能O(1)直接訪問到第k個元素n 單（向）鏈表 ：只能找到下一個節(jié)點(diǎn)n 雙（向）鏈表： 能找到上一個和下一個節(jié)點(diǎn)n 循環(huán)（單、雙）鏈表：首尾相接 形成環(huán)o Java : LinkedListo C+ : STL listo C : 指針3/面試題總體分析o 鏈表的基本

2、操作n插入n刪除n（分組）翻轉(zhuǎn)n排序 Partition、歸并n復(fù)制n歸并排序n找環(huán)、起點(diǎn)、長度n（倒數(shù)）第k個節(jié)點(diǎn)n隨機(jī)返回一個節(jié)點(diǎn)n和其他數(shù)據(jù)結(jié)構(gòu)（二叉樹）相互轉(zhuǎn)換 4/例1 鏈表的插入與刪除o 例1 在單鏈表里插入/刪除一個節(jié)點(diǎn)n 插入o 哪些指針要修改？前驅(qū)的next， 新節(jié)點(diǎn)的nexto 我們要找到插入之前的那個節(jié)點(diǎn)o 特殊情況: 在head之前插入（包括head = NULL)now-next = head;head = now;o 一般情況:在pre后面插入 now-next = pre-next; pre-next = now;5/例1 續(xù)1n 刪除o 哪些指針要修改？前驅(qū)的n

3、exto 我們要找到刪除之前的那個節(jié)點(diǎn)o 特殊情況？ 刪除headtemp = head-next;delete head;head = temp;o 一般情況，在pre后面刪除temp = pre-next;pre-next = temp-next;delete temp;6/例1 續(xù)2o 思考題n 雙向鏈表的插入、刪除n 循環(huán)有序鏈表的插入、刪除 （建議斷開、再連上）n “懶”刪除o 要刪除now這個節(jié)點(diǎn) (不是最后一個）o 把now復(fù)制成now-next n now-x = now-next-xo 刪除now-next7/例2 單鏈表翻轉(zhuǎn)o 例2 單鏈表翻轉(zhuǎn)n思路： 把當(dāng)前節(jié)點(diǎn)拿過來作為

4、已經(jīng)翻轉(zhuǎn)結(jié)果的表頭 （堆棧類似）ListNode *result = 0;while (head) temp = head-next; /保存下一個節(jié)點(diǎn) head-next = result; /當(dāng)前節(jié)點(diǎn)放到結(jié)果的開頭 result = head; /當(dāng)前節(jié)點(diǎn)的頭 head = temp; /head指向下一個節(jié)點(diǎn) return result;8/例2 續(xù)o 思考題n翻轉(zhuǎn)部分鏈表 (Leetcode 92)o如何找到第m個元素和第n個元素o如何處理前面和后面？ n保存前面部分最后一個元素n保存后面部分第一個元素n特殊情況？n每k個元素翻轉(zhuǎn)一次 (Leetcode 25)n前面翻好的部分 （小鏈

5、表）n要翻轉(zhuǎn)的部分(K個）n后面沒處理的部分（小鏈表）n不足k個怎么辦9/例3o 例3 單鏈表里是否有環(huán)？如果有起點(diǎn)是哪里？環(huán)長度是多大？ （最后一個節(jié)點(diǎn)next不是空，而是前面某個節(jié)點(diǎn)） (Leetcode 141, 142)n 方法1 用一個set存放每個節(jié)點(diǎn)地址o 注意: set存放的元素必須“有序”，而地址都是“整數(shù)”set have;for (; head; head = head-next) if (have.find(head) != have.end() return true; have.insert(head);return false;10/例3 續(xù)1o 方法2 不用se

6、t?n 用兩個指針p1和p2, p1每次走一步，p2每次走兩步，如果有圈一定會相遇n 為什么一定會相遇？n 相遇時如何找交點(diǎn)？n 一些變量o 圈長 no 起點(diǎn)到圈的起點(diǎn)距離ao p1到圈起點(diǎn)時，p2在圈中的位置(0= x = y),第一個鏈表先走x y步，再一起走n 方法3: 我們把第一個鏈表首尾相接，連成一個環(huán)，使用例3的方法在第二個鏈表里找圈的起點(diǎn)就是鏈表的交點(diǎn) （最后別忘記恢復(fù)第一個鏈表 從表頭找到表尾,next設(shè)置為空）14/例4 續(xù)15/例5o 例5 一個單鏈表除了next指針外還有一個random指針隨機(jī)指向任何一個元素（可能為空），請復(fù)制它 (Leetcode 138)n 難點(diǎn)：

7、 我們不知道random指針在復(fù)制后鏈表的地址復(fù)制元素地址變了n 方法1 map, 先按照普通方法復(fù)制鏈表，再兩個鏈表同時走復(fù)制random（舊節(jié)點(diǎn)a,新節(jié)點(diǎn)a)a -random = mapa-random （空單獨(dú)處理）16/例5 續(xù)1o 方法2 不用mapn 插入：每個舊節(jié)點(diǎn)后面插入一個自身的“復(fù)本”n 復(fù)制random指針o 一個舊節(jié)點(diǎn)a的復(fù)本是a-nexto a-random的復(fù)本是a-random-nexto 新節(jié)點(diǎn)的random指針a-next-random a-random-next (空值單獨(dú)判斷）n 拆分o 舊節(jié)點(diǎn)鏈表是奇數(shù)項(xiàng)o 新節(jié)點(diǎn)鏈表是偶數(shù)項(xiàng)17/例5 續(xù)218/例6o 例6 鏈表partition 鏈表里存放整數(shù)，給定x把比x小的節(jié)點(diǎn)放到=x之前 (Leetcode 86)19/總結(jié)o 細(xì)致多寫代碼 多練習(xí)n 哪些指針要修改n 修改前保存 （防止鏈表斷掉）n 注意空指針o 特點(diǎn) ：可以重新建立表