有关链表的小技巧,我都给你总结好了
鏈表
鏈表是數(shù)據(jù)結構里一個很基礎但是又很愛考的線性結構,鏈表的操作相對來說比較簡單,但是非常適合考察面試者寫代碼的能力,以及對 corner case 的處理,還有指針的應用很容易引起 NPE (null pointer exception)。綜合以上原因,鏈表在面試中很重要。
提到鏈表就不得不提數(shù)組,它和數(shù)組可以說是數(shù)據(jù)結構的基礎,那么它們最主要的區(qū)別在于:
數(shù)組在物理內存上必須是連續(xù)的
鏈表在物理內存上不需要連續(xù),通過指針連接
所以數(shù)組最好的性質就是可以隨機訪問 random access,有了 index,可以 O(1) 的時間訪問到元素。
而鏈表因為不連續(xù),所以無法 O(1) 的時間定位任意一個元素的位置,那么就只能從頭開始遍歷。
這就造成了它們之間增刪改查上效率的不同。
除此之外,鏈表本身的結構與數(shù)組也是完全不同的。
LinkedList 是由 ListNode 來實現(xiàn)的:
class?ListNode?{int?value;ListNode?next; }結構上長這樣:
這是單向鏈表,那還有的鏈表是雙向鏈表,也就是還有一個 previous pointer 指向當前 node 的前一個 node:
class?ListNode?{int?value;ListNode?next;ListNode?prev; }其實鏈表相關的題目沒有很難的,套路也就這么幾個,其中最常考最基礎的題目是反轉鏈表,聽說微軟可以用這道題電面刷掉一半的 candidate,兩種方法一遍 bug free 還是不容易的。文章之前已經寫過了,點擊這里直達復習。
今天我們來說鏈表中最主要的 2 個技巧:雙指針法和 dummy node,相信看完本文后,鏈表相關的絕大多數(shù)題目你都能搞定啦。
雙指針法
雙指針法在很多數(shù)據(jù)結構和題型中都有應用,在鏈表中用的最多的還是快慢指針。
顧名思義,兩個指針一個走得快,一個走得慢,這樣的好處就是以不同的速度遍歷鏈表,方便找到目標位置。
常見的問題比如找一個鏈表的中點,或者判斷一個鏈表是否有環(huán)。
例 1:找中點
這題就是給一個鏈表,然后找到它的中點,如果是奇數(shù)個很好辦,如果是偶數(shù)個,題目要求返回第二個。
比如:
1 -> 2 -> 3 -> 4 -> 5 -> NULL,需要返回 3 這個 ListNode;
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL,需要返回 4 這個 ListNode。
但其實吐槽一下,如果真的要設計一個這樣的 API,我更傾向于選擇返回偶數(shù)個中的第一個中點。
為什么呢?
算法題都是工業(yè)生產中一些問題的抽象。比如說我們找中點的目的是為了把這個鏈表斷開,那么返回了 3,我可以斷開 3 和 4;但是返回了 4,單向鏈表我怎么斷開 4 之前的地方呢?還得再來一遍,麻煩。
Solution
方法一、
這題最直觀的解法就是可以先求這個鏈表的長度,然后再走這個長度的一半,得到中點。
class?Solution?{public?ListNode?middleNode(ListNode?head)?{if(head?==?null)?{return?null;}int?len?=?0;ListNode?current?=?head;while(current?!=?null)?{len++;current?=?current.next;}len?/=?2;ListNode?result?=?head;while(len?>?0)?{result?=?result.next;len--;}return?result;} }方法二、快慢指針
我們用兩個指針一起來遍歷這個鏈表,每次快指針走 2 步,慢指針走 1 步,這樣當快指針走到頭的時候,慢指針應該剛好在鏈表的中點。
class?Solution?{public?ListNode?middleNode(ListNode?head)?{ListNode?slow?=?head;ListNode?fast?=?head;while(fast?!=?null?&&?fast.next?!=?null)?{slow?=?slow.next;fast?=?fast.next.next;}return?slow;} }這兩個方法孰優(yōu)孰劣呢?
網上很多說什么方法一過了兩遍鏈表,方法二只過了一遍。
但其實,但是方法二用了兩個指針來遍歷,所以兩個方法過的遍數(shù)都是一樣的。
它們最大的區(qū)別是:
方法一是 offline algorithm,方法二是 online algorithm。
公司里的數(shù)據(jù)量是源源不斷的,比如電商系統(tǒng)里總有客戶在下單,社交軟件里的好友增長是一直在漲的,這些是數(shù)據(jù)流 data stream,我們是無法計算數(shù)據(jù)流的長度的。
那么 online algorithm 能夠給時刻給出當前的結果,不用說等數(shù)據(jù)全部錄入完成后,實際上也錄不完。。這是 online algorithm 比 offline algorithm 大大的優(yōu)勢所在。
更多的解釋大家可以參考 stack overflow 的這個問題[1],鏈接在文末。
例 2:判斷單鏈表是否有環(huán)
思路:快慢指針一起從 head 出發(fā),每次快指針走 2 步,慢指針只走 1 步,如果存在環(huán),那么兩個指針一定會相遇。
這題是典型的龜兔賽跑,或者說在操場跑圈時,跑的快的同學總會套圈跑的慢的。
public?class?Solution?{public?boolean?hasCycle(ListNode?head)?{ListNode?slow?=?head;ListNode?fast?=?head;while(fast?!=?null?&&?fast.next?!=?null)?{slow?=?slow.next;fast?=?fast.next.next;if(slow?==?fast)?{return?true;}}return?false;} }這題有個升級版,就是要求返回環(huán)的起點。
例 3:返回有環(huán)鏈表的環(huán)的起點
這題我感覺不全是個算法題了,還是個數(shù)學題哈哈。
先擺出結論:
快慢指針從鏈表頭開始走,相遇的那點,記為 M;
再用 2 個指針,一個從頭開始走,一個從 M 開始走,相遇點即為 cycle 的起點。
我們先看抽象出來的圖:
假設快慢指針在 M 點第一次相遇,
這里我們設 3 個變量來表示這個鏈表里的幾個重要長度:
X:從鏈表頭到環(huán)的起點的長度;
Y:從環(huán)的起點到 M 點的長度;
Z:從 M 點到環(huán)的起點的長度。
注意:因為環(huán)是有方向的,所以 Y 并不是 Z。
那其實我們唯一知道的關系就是:快慢指針在 M 點第一次相遇。這也是我們最初假設的關系。
而快慢指針有一個永遠不變的真理:快指針走的長度永遠是慢指針走的長度的 2 倍。
相遇時快慢指針分別走了多少的長度呢?
快指針:X+ Y + 假設走了 k 圈
慢指針:X + Y
那么我們就可以用這個 2 倍的關系,列出下列等式:
2 * (X + Y) = X + Y + kL
所以 X + Y = kL
而我們注意到:Y + Z = L,那么就能得出 X = Z。
所以當兩個指針,一個從頭開始走,一個從 M 點開始走時,相遇那點就是環(huán)的起點,證畢。
來看下代碼吧:
public?class?Solution?{public?ListNode?detectCycle(ListNode?head)?{ListNode?slow?=?head;ListNode?fast?=?head;while?(fast?!=?null?&&?fast.next?!=?null)?{slow?=?slow.next;fast?=?fast.next.next;if?(slow?==?fast)?{ListNode?x?=?head;ListNode?y?=?slow;while(x?!=?y)?{x?=?x.next;y?=?y.next;}return?x;}}return?null;} }這題還有個應用,就是找一個特定數(shù)組里重復的數(shù)字,這里就不展開了,大家感興趣的去做一下吧~
接下來我們聊聊 dummy node 這個技巧。
Dummy node
Dummy 的中文是“假”的意思,dummy node 大概可以翻譯成虛擬節(jié)點?有更地道的說法的話還請大家在評論區(qū)告訴我呀~
一般來說,dummy node 的用法是在鏈表的真實 head 的前面加一個指向這個 head 的節(jié)點,目的是為了方便操作 head。
對于鏈表來說,head 是一個鏈表的靈魂,因為無論是查詢還是其他的操作都需要從頭開始,俗話說擒賊先擒王嘛,抓住了一個鏈表的頭,就抓住了整個鏈表。
所以當需要對現(xiàn)有鏈表的頭進行改動時,或者不確定頭部節(jié)點是哪個,我們可以預先加一個 dummyHead,這樣就可以靈活處理鏈表中的剩余部分,最后返回時去掉這個“假頭”就好了。
很多時候 dummy node 不是必須,但是用了會很方便,減少 corner case 的討論,所以還是非常推薦使用的。
光說不練假把式,我們直接來看題~
例 4:合并兩個排好序的鏈表
這題有很多種解法,比如最直觀的就是用兩個指針,然后比較大小,把小的接到最終的結果上去。
但是有點麻煩的是,最后的結果不知道到底誰是頭啊,是哪個鏈表的頭作為了最終結果的頭呢?
這種情況就非常適合用 dummy node。
先用一個虛擬的頭在這撐著,把整個鏈表構造好之后,再把這個假的剔除。
來看代碼~
class?Solution?{public?ListNode?mergeTwoLists(ListNode?l1,?ListNode?l2)?{if?(l1?==?null)?{return?l2;}if?(l2?==?null)?{return?l1;}ListNode?dummy?=?new?ListNode(0);ListNode?ptr?=?dummy;while?(l1?!=?null?&&?l2?!=?null)?{if?(l1.val?<?l2.val)?{ptr.next?=?l1;l1?=?l1.next;}?else?{ptr.next?=?l2;l2?=?l2.next;}ptr?=?ptr.next;}if?(l1?==?null)?{ptr.next?=?l2;}?else?{ptr.next?=?l1;}return?dummy.next;} }這題也有升級版,就是合并 k 個排好序的鏈表。本質上也是一樣的,只不過需要重寫一下比較器就好了。
例 5:刪除節(jié)點
這道題的意思是刪除鏈表中某個特定值的節(jié)點,可能有一個可能有多個,可能在頭可能在尾。
如果要刪除的節(jié)點在頭的時候,新鏈表的頭就不確定了,也有可能是個空的。。此時就很適合用 dummy node 來做,規(guī)避掉這些 corner case 的討論。
那這題的思路就是:用 2 個指針
prev:指向當前新鏈表的尾巴
curr:指向當前正在遍歷的 ListNode
如果 curr == 目標值,那就直接移到下一個;
如果 curr != 目標值,那就把 prev 指向它,接上。
這題需要注意的是,最后一定要把 prev.next 指向 null,否則如果原鏈表的尾巴是目標值的話,還是去不掉。
代碼如下:
class?Solution?{public?ListNode?removeElements(ListNode?head,?int?val)?{ListNode?dummy?=?new?ListNode(0);ListNode?prev?=?dummy;ListNode?curr?=?head;while(curr?!=?null)?{if?(curr.val?!=?val)?{prev.next?=?curr;prev?=?prev.next;}curr?=?curr.next;}prev.next?=?null;return?dummy.next;} }好了,以上就是本文的所有內容了,如果這篇文章對你有幫助,歡迎分享給你身邊的朋友,也給我點個「在看」,你們的支持是我創(chuàng)作的最大動力!
往期推薦鏈表反轉的兩種實現(xiàn)方法,后一種擊敗了100%的用戶!
漫畫:如何找到鏈表的倒數(shù)第n個結點?
算法圖解:如何用兩個棧實現(xiàn)一個隊列?
關注我,每天陪你進步一點點!
總結
以上是生活随笔為你收集整理的有关链表的小技巧,我都给你总结好了的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: c#官方推荐md5通用加密类
- 下一篇: 【面试收藏】Redis最全面试题