面試大總結(jié)Java搞定面試中的鏈表題目總結(jié).pdf

面面試大總結(jié) Java搞定面試中的鏈表題目總結(jié) 試大總結(jié) Java搞定面試中的鏈表題目總結(jié) 鏈表是面試中常出現(xiàn)的一類題目 本文用Java實(shí)現(xiàn)了面試中常見的鏈表相關(guān)題目 本文主要參考整合重寫了 輕松 搞定面試中的鏈表題目 和 算法大全 1 單鏈表 兩篇大作 兩篇大神的實(shí)現(xiàn)分別是C和C 因?yàn)槲腋矚g用 Java面試 所以用Java重寫了所有實(shí)現(xiàn) 并附上自己的一些思考注釋 算法大全 1 單鏈表 尚未有一些問題尚未 整合進(jìn)來(lái) 很快我會(huì)更新本文 接下來(lái)還會(huì)出關(guān)于二叉樹的大總結(jié)和棧和隊(duì)列的大總結(jié) 因?yàn)檫@些都屬于面試中的送 分題 必須毫無(wú)偏差地拿下 至于像動(dòng)態(tài)規(guī)劃這些比較 高端 的算法 就只能靠日積月累 而不能像這樣臨時(shí)突 擊了 package LinkedListSummary import java util HashMap import java util Stack 輕松搞定面試中的鏈表題目 算法大全 1 單鏈表 目錄 1 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù) getListLength 2 將單鏈表反轉(zhuǎn) reverseList 遍歷 reverseListRec 遞歸 3 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn) k 0 reGetKthNode 4 查找單鏈表的中間結(jié)點(diǎn) getMiddleNode 5 從尾到頭打印單鏈表 reversePrintListStack reversePrintListRec 遞歸 6 已知兩個(gè)單鏈表pHead1 和pHead2 各自有序 把它們合并成一個(gè)鏈表依然有序 mergeSortedList mergeSortedListRec 7 判斷一個(gè)單鏈表中是否有環(huán) hasCycle 8 判斷兩個(gè)單鏈表是否相交 isIntersect 9 求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn) getFirstCommonNode 10 已知一個(gè)單鏈表中存在環(huán) 求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn) getFirstNodeInCycle getFirstNodeInCycleHashMap 11 給出一單鏈表頭指針pHead和一節(jié)點(diǎn)指針pToBeDeleted O 1 時(shí)間復(fù)雜度刪除節(jié)點(diǎn)pToBeDeleted delete public class Demo public static void main String args Node n1 new Node 1 Node n2 new Node 2 Node n3 new Node 3 Node n4 new Node 4 Node n5 new Node 5 n1 next n2 n2 next n3 n3 next n4 n4 next n5 printList n1 System out println getListLength n1 Node head reverseList n1 Node head reverseListRec n1 printList head Node x reGetKthNode head 2 System out println x val x getMiddleNode head System out println x val System out println reversePrintListStack reversePrintListStack head 1 System out println reversePrintListRec reversePrintListRec head private static class Node int val Node next public Node int val this val val public static void printList Node head while head null System out print head val head head next System out println 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù) 注意檢查鏈表是否為空 時(shí)間復(fù)雜度為O n public static int getListLength Node head 注意頭結(jié)點(diǎn)為空情況 if head null return 0 int len 0 Node cur head while cur null len cur cur next return len 翻轉(zhuǎn)鏈表 遍歷 從頭到尾遍歷原鏈表 每遍歷一個(gè)結(jié)點(diǎn) 將其摘下放在新鏈表的最前端 注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況 時(shí)間復(fù)雜度為O n public static Node reverseList Node head 如果鏈表為空或只有一個(gè)節(jié)點(diǎn) 無(wú)需反轉(zhuǎn) 直接返回原鏈表表頭 if head null head next null return head Node reHead null 反轉(zhuǎn)后新鏈表指針 Node cur head while cur null Node preCur cur 用preCur保存住對(duì)要處理節(jié)點(diǎn)的引用 cur cur next cur更新到下一個(gè)節(jié)點(diǎn) preCur next reHead 更新要處理節(jié)點(diǎn)的next引用 reHead preCur reHead指向要處理節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) return reHead 翻轉(zhuǎn)遞歸 遞歸 遞歸的精髓在于你就默認(rèn)reverseListRec已經(jīng)成功幫你解決了子問題了 但別去想如何解決的 現(xiàn)在只要處理當(dāng)前node和子問題之間的關(guān)系 最后就能圓滿解決整個(gè)問題 head 2 1 2 3 4 head 1 4 3 2 Node reHead reverseListRec head next reHead head next 4 3 2 1 head next next head reHead 4 3 2 1 null head next null reHead public static Node reverseListRec Node head if head null head next null return head Node reHead reverseListRec head next head next next head 把head接在reHead串的最后一個(gè)后面 head next null 防止循環(huán)鏈表 return reHead 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn) k 0 最普遍的方法是 先統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的個(gè)數(shù) 然后再找到第 n k 個(gè)結(jié)點(diǎn) 注意鏈表為空 k為0 k為1 k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)時(shí)的情況 時(shí)間復(fù)雜度為O n 代碼略 這里主要講一下另一個(gè)思路 這種思路在其他題目中也會(huì)有應(yīng)用 主要思路就是使用兩個(gè)指針 先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn) 這樣前后兩個(gè)指針的距離差是k 1 之后前后兩個(gè)指針一起向前走 前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí) 后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn) public static Node reGetKthNode Node head int k 這里k的計(jì)數(shù)是從1開始 若k為0或鏈表為空返回null if k 0 head null return null Node q head q在p前面 p q Node p head p在q后面 讓q領(lǐng)先p距離k while k 1 k 當(dāng)節(jié)點(diǎn)數(shù)小于k 返回null if k 1 q null return null 前后兩個(gè)指針一起走 直到前面的指針指向最后一個(gè)節(jié)點(diǎn) while q next null p p next q q next 當(dāng)前面的指針指向最后一個(gè)節(jié)點(diǎn)時(shí) 后面的指針指向倒數(shù)k個(gè)節(jié)點(diǎn) return p 查找單鏈表的中間結(jié)點(diǎn) 此題可應(yīng)用于上一題類似的思想 也是設(shè)置兩個(gè)指針 只不過(guò)這里是 兩個(gè)指針同時(shí)向前走 前面的指針每次走兩步 后面的指針每次走一步 前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí) 后面的指針?biāo)附Y(jié)點(diǎn)就是中間結(jié)點(diǎn) 即第 n 2 1 個(gè)結(jié)點(diǎn) 注意鏈表為空 鏈表結(jié)點(diǎn)個(gè)數(shù)為1和2的情況 時(shí)間復(fù)雜度O n 3 public static Node getMiddleNode Node head if head null head next null return head Node q head p q Node p head 前面指針每次走兩步 直到指向最后一個(gè)結(jié)點(diǎn) 后面指針每次走一步 while q next null q q next p p next if q next null q q next return p 從尾到頭打印單鏈表 對(duì)于這種顛倒順序的問題 我們應(yīng)該就會(huì)想到棧 后進(jìn)先出 所以 這一題要么自己使用棧 要么讓系統(tǒng)使用棧 也就是遞歸 注意鏈表為空的情況 時(shí)間復(fù)雜度為O n public static void reversePrintListStack Node head Stack s new Stack Node cur head while cur null s push cur cur cur next while s empty cur s pop System out print cur val System out println 從尾到頭打印鏈表 使用遞歸 優(yōu)雅 public static void reversePrintListRec Node head if head null return else reversePrintListRec head next System out print head val 已知兩個(gè)單鏈表pHead1 和pHead2 各自有序 把它們合并成一個(gè)鏈表依然有序 這個(gè)類似歸并排序 尤其注意兩個(gè)鏈表都為空 和其中一個(gè)為空時(shí)的情況 只需要O 1 的空間 時(shí)間復(fù)雜度為O max len1 len2 public static Node mergeSortedList Node head1 Node head2 其中一個(gè)鏈表為空的情況 直接返回另一個(gè)鏈表頭 O 1 if head1 null return head2 if head2 null return head1 Node mergeHead null 先確定下來(lái)mergeHead是在哪里 if head1 val head2 val 4 mergeHead head1 mergeHead next null 斷開mergeHead和后面的聯(lián)系 head1 head1 next 跳過(guò)已經(jīng)合并了的元素 else mergeHead head2 mergeHead next null head2 head2 next Node mergeCur mergeHead while head1 null 把找到較小的元素合并到merge中 head1 head1 next 跳過(guò)已經(jīng)合并了的元素 mergeCur mergeCur next 找到下一個(gè)準(zhǔn)備合并的元素 mergeCur next null 斷開mergeCur和后面的聯(lián)系 else mergeCur next head2 head2 head2 next mergeCur mergeCur next mergeCur next null 合并剩余的元素 if head1 null mergeCur next head1 else if head2 null mergeCur next head2 return mergeHead 遞歸合并兩鏈表 優(yōu)雅 public static Node mergeSortedListRec Node head1 Node head2 if head1 null return head2 if head2 null return head1 Node mergeHead null if head1 val head2 val mergeHead head1 連接已解決的子問題 mergeHead next mergeSortedListRec head1 head2 else mergeHead head2 mergeHead next mergeSortedListRec head1 head2 return mergeHead 判斷一個(gè)單鏈表中是否有環(huán) 這里也是用到兩個(gè)指針 如果一個(gè)鏈表中有環(huán) 也就是說(shuō)用一個(gè)指針去遍歷 是永遠(yuǎn)走不到頭的 因此 我們可以用兩個(gè)指針去遍歷 一個(gè)指針一次走兩步 一個(gè)指針一次走一步 如果有環(huán) 兩個(gè)指針肯定會(huì)在環(huán)中相遇 時(shí)間復(fù)雜度為O n public static boolean hasCycle Node head Node fast head 快指針每次前進(jìn)兩步 Node slow head 慢指針每次前進(jìn)一步 while fast null slow slow next if fast slow 相遇 存在環(huán) return true return false 判斷兩個(gè)單鏈表是否相交 如果兩個(gè)鏈表相交于某一節(jié)點(diǎn) 那么在這個(gè)相交節(jié)點(diǎn)之后的所有節(jié)點(diǎn)都是兩個(gè)鏈表所共有的 也就是說(shuō) 如果兩個(gè)鏈表相交 那么最后一個(gè)節(jié)點(diǎn)肯定是共有的 先遍歷第一個(gè)鏈表 記住最后一個(gè)節(jié)點(diǎn) 然后遍歷第二個(gè)鏈表 到最后一個(gè)節(jié)點(diǎn)時(shí)和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)做比較 如果相同 則相交 否則不相交 時(shí)間復(fù)雜度為O len1 len2 因?yàn)橹恍枰粋€(gè)額外指針保存最后一個(gè)節(jié)點(diǎn)地址 空間復(fù)雜度為O 1 public static boolean isIntersect Node head1 Node head2 if head1 null head2 null return false Node tail1 head1 找到鏈表1的最后一個(gè)節(jié)點(diǎn) while tail1 next null tail1 tail1 next Node tail2 head2 找到鏈表2的最后一個(gè)節(jié)點(diǎn) while tail2 next null tail2 tail2 next return tail1 tail2 求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn) 對(duì)第一個(gè)鏈表遍歷 計(jì)算長(zhǎng)度len1 同時(shí)保存最后一個(gè)節(jié)點(diǎn)的地址 對(duì)第二個(gè)鏈表遍歷 計(jì)算長(zhǎng)度len2 同時(shí)檢查最后一個(gè)節(jié)點(diǎn)是否和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)相同 若不相同 不相交 結(jié)束 兩個(gè)鏈表均從頭節(jié)點(diǎn)開始 假設(shè)len1大于len2 那么將第一個(gè)鏈表先遍歷len1 len2個(gè)節(jié)點(diǎn) 此時(shí)兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)到第一個(gè)相交節(jié)點(diǎn)的距離就相等了 然后一起向后遍歷 直到兩個(gè)節(jié)點(diǎn)的地址相同 時(shí)間復(fù)雜度 O len1 len2 len2 len1 len2 int k len1 len2 while k 0 n1 n1 next k else int k len2 len1 while k 0 n2 n2 next k 一起向后遍歷 直到找到交點(diǎn) while n1 n2 n1 n1 next n2 n2 next return n1 求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn) 用快慢指針做 本題用了Crack the Coding Interview的解法 因?yàn)楦?jiǎn)潔易懂 public static Node getFirstNodeInCycle Node head Node slow head Node fast head 1 找到快慢指針相遇點(diǎn) while fast null fast fast next next if slow fast Collision break 錯(cuò)誤檢查 這是沒有環(huán)的情況 if fast null fast next null return null 2 現(xiàn)在 相遇點(diǎn)離環(huán)的開始處的距離等于鏈表頭到環(huán)開始處的距離 這樣 我們把慢指針放在鏈表頭 快指針保持在相遇點(diǎn) 然后 同速度前進(jìn) 再次相遇點(diǎn)就是環(huán)的開始處 slow head while slow fast slow slow next fast fast next 再次相遇點(diǎn)就是環(huán)的開始處 return fast 求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn) 用HashMap做 一個(gè)無(wú)環(huán)的鏈表 它每個(gè)結(jié)點(diǎn)的地址都是不一樣的 7 但如果有環(huán) 指針沿著鏈表移動(dòng) 那這個(gè)指針最終會(huì)指向一個(gè)已經(jīng)出現(xiàn)過(guò)的地址 以地址為哈希表的鍵值 每出現(xiàn)一個(gè)地址 就將該鍵值對(duì)應(yīng)的實(shí)值置為true 那么當(dāng)某個(gè)鍵值對(duì)應(yīng)的實(shí)值已經(jīng)為true時(shí) 說(shuō)明這個(gè)地址之前已經(jīng)出現(xiàn)過(guò)了 直接返回它就OK了 public st