1象对、鏈表基礎(chǔ)
-
鏈?zhǔn)酱鎯Ψ绞骄€性表
- 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素勒魔，這組存儲單元可以是連續(xù)的杨名，也可以是不連續(xù)的.
- 優(yōu)：刪除還插入效率高
- 缺：查詢效率低
-
循環(huán)鏈表
- 將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點斥黑，就使整個單鏈表形成一個環(huán)喊式，這種頭尾相連的單鏈表稱為單循環(huán)鏈表岔留，簡稱循環(huán)鏈表.
- 雙向循環(huán)鏈表是單向循環(huán)鏈表的每個結(jié)點中检柬，再設(shè)置一個指向其前驅(qū)結(jié)點的指針域
-
1何址、單鏈表的打印
2用爪、鏈表的逆序
- 3偎血、已知鏈表的頭節(jié)點指針head烁巫，將鏈表從位置m到n 逆序（不可申請額外的空間）亚隙。
- 4阿弃、已知鏈表A的頭節(jié)點指針headA,鏈表B的頭節(jié)點指針headB渣淳， 兩個鏈表相交入愧，求兩個鏈表交點對應(yīng)的節(jié)點。
- 思路1:使用set求交集
- 遍歷鏈表A ，將A中節(jié)點對應(yīng)的指針地址桦踊，插入set.
-
遍歷鏈表B终畅，將B中節(jié)點對應(yīng)的指針地址，在set 中查找炼蛤，發(fā)現(xiàn)在set 中的第一個節(jié)點地址鲸湃，既是兩個鏈表的交點子寓。
- 思路2：
- 計算headA 鏈表的長度、計算headB鏈表的長度鲜屏，較長的鏈表多出的長度国拇。
- 將較長鏈表的指針移動到和較短鏈表指針對齊的位置
- 將headA 與headB同時移動酱吝，當(dāng)兩個指針指向同一個節(jié)點時务热，找到了。
- 5、已知鏈表可能存在環(huán)绩卤，若有環(huán)返回環(huán)起始節(jié)點江醇，否則返回NULL
- 思路1:使用set求交集
- 遍歷鏈表 跋炕，將鏈表中節(jié)點對應(yīng)的指針地址律适，插入set.
- 在遍歷鏈表時，在set 中查找胳嘲，第一個在set 中發(fā)現(xiàn)的節(jié)點地址了牛，既是鏈表的起點鹰祸。
- 思路2:快慢指針賽跑
- 快指針每次走2步蛙婴，慢指針走1步.
- 如果有環(huán)尔破，必定相遇懒构。從head與meet 出發(fā)胆剧，兩指針?biāo)俣纫粯釉蘩担嘤鰰r即為環(huán)的起點。
- 6匿垄、已知鏈表頭指針與數(shù)值x,將所有小于x 的節(jié)點放在大于或者等于x的節(jié)點前椿疗，且保持這些節(jié)點的原來的相對位置。
- 思路：巧用臨時頭節(jié)點。
- 7靖苇、已知一個復(fù)雜的鏈表贤壁，節(jié)點中有一個指向本鏈表任意某個節(jié)點的隨機指針脾拆，求這個鏈表的深度拷貝。
前期的準(zhǔn)備工作：
- 設(shè)置一個節(jié)點map,key為節(jié)點地址，value為整型渔期。
思路：
難點在于：將原鏈表的random指針的指向關(guān)系理清楚拘哨，如何保存。
-
知識儲備：
vector是表示可變大小數(shù)組的序列容器瓮床。
就像數(shù)組一樣隘庄，vector也采用的連續(xù)存儲空間來存儲元素丑掺。也就是意味著可以采用下標(biāo)對vector的元素進行訪問街州，和數(shù)組一樣高效玻孟。但是又不像數(shù)組黍翎，它的大小是可以動態(tài)改變的匣掸，而且它的大小會被容器自動處理。
本質(zhì)講眶蕉，vector使用動態(tài)分配數(shù)組來存儲它的元素造挽。當(dāng)新元素插入時候弄痹，這個數(shù)組需要被重新分配大小為了增加存儲空間肛真。其做法是蚓让，分配一個新的數(shù)組，然后將全部元素移到這個數(shù)組窄瘟。就時間而言蹄葱，這是一個相對代價高的任務(wù)图云，因為每當(dāng)一個新的元素加入到容器的時候竣况，vector并不會每次都重新分配大小饶囚。
vector分配空間策略：vector會分配一些額外的空間以適應(yīng)可能的增長帕翻，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權(quán)衡空間的使用和重新分配萝风。但是無論如何嘀掸，重新分配都應(yīng)該是對數(shù)增長的間隔大小，以至于在末尾插入一個元素的時候是在常數(shù)時間的復(fù)雜度完成的规惰。
因此睬塌，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態(tài)增長揩晴。
與其它動態(tài)序列容器相比（deques, lists and forward_lists）， vector在訪問元素的時候更加高效硫兰，在末尾添加和刪除元素相對高效诅愚。對于其它不在末尾的刪除和插入操作，效率更低劫映。比起lists和forward_lists統(tǒng)一的迭代器和引用更好违孝。
多個元素賦值： vec.assign(); //類似于初始化時用數(shù)組進行賦值
末尾添加元素： vec.push_back();
末尾刪除元素： vec.pop_back();
任意位置插入元素： vec.insert();
任意位置刪除元素： vec.erase();
交換兩個向量的元素： vec.swap();
清空向量元素： vec.clear();
- 1： 創(chuàng)建地址到節(jié)點位置的map。
- 2: 使用Vector根據(jù)存儲節(jié)點位置訪問地址泳赋。
- 3: 循環(huán)遍歷雌桑，將新鏈表節(jié)點push 入node_vec，生成了新鏈表節(jié)點位置到地址的map祖今。
- 4: 記錄原始鏈表地址至節(jié)點位置的node_map校坑。
- 5: 遍歷原始鏈表。
- 6: 記錄節(jié)點位置千诬。
-
7: 再次遍歷原始鏈表耍目，鏈接新鏈表的next指針，random 指針大渤。
- 8制妄、已知兩個已排序鏈表頭節(jié)點指針式headA ,headB,將兩個鏈表合并，合并后仍為有序的泵三，返回合并的頭節(jié)點。
- 思路： 建立一個臨時頭節(jié)點 temp_head. 然后讓pre指針指向該節(jié)點衔掸。 比較headA,headB指向的節(jié)點烫幕，將較小的節(jié)點插入pre 指針后，并向前移動較小節(jié)點對應(yīng)的指針敞映。
- 9较曼、已知K個已排序鏈表頭節(jié)點指針，將這K個鏈表合并振愿，合并后仍為有序的捷犹，返回合并后的頭節(jié)點。
方案1:
方案2：
241天以來冕末，Java架構(gòu)更新了 602個主題萍歉，已經(jīng)有100+位同學(xué)加入。微信掃碼關(guān)注java架構(gòu)档桃，獲取Java面試題和架構(gòu)師相關(guān)題目和視頻枪孩。上述相關(guān)面試題答案，盡在Java架構(gòu)中。
