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

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