面試 7：面試常見(jiàn)的鏈表類算法捷徑
鏈表是我們數(shù)據(jù)結(jié)構(gòu)面試中比較容易出錯(cuò)的問(wèn)題寝并，所以很多面試官總喜歡在這上面下功夫申尼，為了避免出錯(cuò)胶惰，我們最好先進(jìn)行全面的分析惦界。在實(shí)際軟件開發(fā)周期中挑格，設(shè)計(jì)的時(shí)間通常不會(huì)比編碼的時(shí)間短，在面試的時(shí)候我們不要著急于寫代碼沾歪，而是一開始仔細(xì)分析和設(shè)計(jì)漂彤，這將給面試官留下一個(gè)很好的印象。
與其很快寫出一段千瘡百孔的代碼灾搏，不容仔細(xì)分析后再寫出健壯性無(wú)敵的程序挫望。
面試題：輸入一個(gè)單鏈表的頭結(jié)點(diǎn)，返回它的中間元素狂窑。為了方便媳板，元素值用整型表示。
當(dāng)應(yīng)聘者看到這道題的時(shí)候泉哈，內(nèi)心一陣狂喜蛉幸，怎么給自己遇到了這么簡(jiǎn)單的題。拿起筆就開始寫旨巷，先遍歷整個(gè)鏈表巨缘，拿到鏈表的長(zhǎng)度 len，再次遍歷鏈表采呐，位于 len/2 的元素就是鏈表的中間元素若锁。
所以這個(gè)題最重要的點(diǎn)就是拿到鏈表的長(zhǎng)度 len。而拿到這個(gè) len 也比較簡(jiǎn)單斧吐，只需要遍歷前設(shè)定一個(gè) count 值又固，遍歷的時(shí)候 count++ ，第一次遍歷結(jié)束煤率，就拿到單鏈表的長(zhǎng)度 len 了仰冠。
于是我們很快寫出了這樣的代碼：
public class Test15 {
public static class LinkNode {
int data;
LinkNode next;
public LinkNode(int data) {
this.data = data;
}
}
private static int getTheMid(LinkNode head) {
int count = 0;
LinkNode node = head;
while (head != null) {
head = head.next;
count++;
}
for (int i = 0; i < count / 2; i++) {
node = node.next;
}
return node.data;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(1);
head.next = new LinkNode(2);
head.next.next = new LinkNode(3);
head.next.next.next = new LinkNode(4);
head.next.next.next.next = new LinkNode(5);
System.out.println(getTheMid(head));
}
}
面試官看到這個(gè)代碼的時(shí)候，他告訴我們上面代碼循環(huán)了兩次蝶糯，但是他期待的只有一次洋只。
于是我們絞盡腦汁，突然想到了網(wǎng)上介紹過(guò)的一個(gè)概念：快慢指針?lè)?/strong>昼捍。
假設(shè)我們?cè)O(shè)置兩個(gè)變量 slow识虚、fast 起始都指向單鏈表的頭結(jié)點(diǎn)當(dāng)中，然后依次向后面移動(dòng)妒茬，fast 的移動(dòng)速度是 slow 的 2 倍担锤。這樣當(dāng) fast 指向末尾節(jié)點(diǎn)的時(shí)候，slow 就正好在正中間了乍钻。
想清楚這個(gè)思路后肛循，我們很快就能寫出如下代碼：
public class Test15 {
public static class LinkNode {
int data;
LinkNode next;
public LinkNode(int data) {
this.data = data;
}
}
private static int getTheMid(LinkNode head) {
LinkNode slow = head;
LinkNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow.data;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(1);
head.next = new LinkNode(2);
head.next.next = new LinkNode(3);
head.next.next.next = new LinkNode(4);
head.next.next.next.next = new LinkNode(5);
System.out.println(getTheMid(head));
}
}
快慢指針?lè)ㄅe一反三
快慢指針?lè)?/strong> 確實(shí)在鏈表類面試題中特別好用铭腕，我們不妨在這里舉一反三，對(duì)原題稍微修改一下多糠，其實(shí)也可以實(shí)現(xiàn)累舷。
面試題：給定一個(gè)單鏈表的頭結(jié)點(diǎn)，判斷這個(gè)鏈表是否是循環(huán)鏈表熬丧。
和前面的問(wèn)題一樣笋粟，我們只需要定義兩個(gè)變量 slow，fast析蝴，同時(shí)從鏈表的頭結(jié)點(diǎn)出發(fā)害捕，fast 每次走鏈表，而 slow 每次只走一步闷畸。如果走得快的指針追上了走得慢的指針尝盼，那么鏈表就是環(huán)形(循環(huán))鏈表。如果走得快的指針走到了鏈表的末尾（fast.next 指向 null）都沒(méi)有追上走得慢的指針佑菩，那么鏈表就不是環(huán)形鏈表盾沫。
有了這樣的思路，實(shí)現(xiàn)代碼那還不是分分鐘的事兒殿漠。
public class Test15 {
public static class LinkNode {
int data;
LinkNode next;
public LinkNode(int data) {
this.data = data;
}
}
private static boolean isRingLink(LinkNode head) {
LinkNode slow = head;
LinkNode fast = head;
while (slow != null && fast != null && fast.next != null) {
if (slow == fast || fast.next == slow) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(1);
head.next = new LinkNode(2);
head.next.next = new LinkNode(3);
head.next.next.next = new LinkNode(4);
head.next.next.next.next = new LinkNode(5);
System.out.println(isRingLink(head));
head.next.next.next.next.next = head;
System.out.println(isRingLink(head));
}
}
確實(shí)有意思赴精，快慢指針?lè)?/strong> 再一次利用它的優(yōu)勢(shì)巧妙解決了我們的問(wèn)題。
快慢指針?lè)ǖ难诱?/h4>
我們上面講解的「快慢指針?lè)ā咕且粋€(gè)變量走 1 步绞幌，一個(gè)變量走 n 步蕾哟。我們其實(shí)還可以拓展它。這個(gè)「快慢」并不是說(shuō)一定要同時(shí)遍歷莲蜘。
比如《劍指Offer》中的第 15 道面試題谭确，就運(yùn)用到了「快慢指針?lè)ā沟难诱埂?/p>
面試題：輸入一個(gè)單鏈表的頭結(jié)點(diǎn)，輸出該鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)的值票渠。
初一看這個(gè)似乎并不像我們前面學(xué)習(xí)到的「快慢指針?lè)ā沟目疾熘鸸Ｋ源蠖鄶?shù)人就迷糊了，進(jìn)入到常規(guī)化思考问顷。依然還是設(shè)置一個(gè)整型變量 count昂秃，然后每次循環(huán)的時(shí)候 count++，拿到鏈表的長(zhǎng)度 n杜窄。那么倒數(shù)第 k 個(gè)節(jié)點(diǎn)也就是順數(shù)第 n-k+1 個(gè)結(jié)點(diǎn)肠骆。所以我們只需要在拿到長(zhǎng)度 n 后再進(jìn)行一次 n-k+1 次循環(huán)就可以拿到這個(gè)倒數(shù)第 k 個(gè)節(jié)點(diǎn)的值了。
但面試官顯然不會(huì)太滿意這個(gè)臃腫的解法羞芍，他依然希望我們一次循環(huán)就能搞定這個(gè)事哗戈。
為了實(shí)現(xiàn)只遍歷一次鏈表就能找到倒數(shù)第 k 個(gè)結(jié)點(diǎn)郊艘，我們依然可以定義兩個(gè)遍歷 slow 和 fast荷科。我們讓 fast 變量先往前遍歷 k-1 步唯咬，slow 保持不動(dòng)。從第 k 步開始畏浆，slow 變量也跟著 fast 變量從鏈表的頭結(jié)點(diǎn)開始遍歷胆胰。由于兩個(gè)變量指向的結(jié)點(diǎn)距離始終保持在 k-1，那么當(dāng) fast 變量到達(dá)鏈表的尾結(jié)點(diǎn)的時(shí)候刻获，slow 變量指向的結(jié)點(diǎn)正好是我們所需要的倒數(shù)第 k 個(gè)結(jié)點(diǎn)蜀涨。
我們依然可以在心中默認(rèn)一遍代碼：
- 假設(shè)輸入的鏈表是：1->2->3->4->5；
- 現(xiàn)在我們要求倒數(shù)第三個(gè)結(jié)點(diǎn)的值蝎毡，即順數(shù)第 3 個(gè)結(jié)點(diǎn)厚柳，它的值為 3；
- 定義兩個(gè)變量 slow沐兵、fast别垮，它們均指向結(jié)點(diǎn) 1；
- 先讓 fast 向前走 k-1 即 2 步扎谎，這時(shí)候 fast 指向了第 3 個(gè)結(jié)點(diǎn)碳想，它的值是 3；
- 現(xiàn)在 fast 和 slow 同步向右移動(dòng)毁靶；
- fast 再經(jīng)過(guò)了 2 步到達(dá)了鏈表尾結(jié)點(diǎn)胧奔；fast 正好指向了第 3 個(gè)結(jié)點(diǎn)，這顯然是符合我們的猜想的预吆。
在心中默走了一遍代碼后龙填，我們顯然很容易寫出下面的代碼。
public class Test15 {
public static class LinkNode {
int data;
LinkNode next;
public LinkNode(int data) {
this.data = data;
}
}
private static int getSpecifiedNodeReverse(LinkNode head, int k) {
LinkNode slow = head;
LinkNode fast = head;
if (fast == null) {
throw new RuntimeException("your linkNode is null");
}
// 先讓 fast 先走 k-1 步
for (int i = 0; i < k - 1; i++) {
if (fast.next == null) {
// 說(shuō)明輸入的 k 已經(jīng)超過(guò)了鏈表長(zhǎng)度啡浊，直接報(bào)錯(cuò)
throw new RuntimeException("the value k is too large.");
}
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow.data;
}
public static void main(String[] args) {
LinkNode head = new LinkNode(1);
head.next = new LinkNode(2);
head.next.next = new LinkNode(3);
head.next.next.next = new LinkNode(4);
head.next.next.next.next = new LinkNode(5);
System.out.println(getSpecifiedNodeReverse(head, 3));
System.out.println(getSpecifiedNodeReverse(null, 1));
}
}
總結(jié)
鏈表類面試題觅够，真是可以玩出五花八門，當(dāng)我們用一個(gè)變量遍歷鏈表不能解決問(wèn)題的時(shí)候巷嚣，我們可以嘗試用兩個(gè)變量來(lái)遍歷鏈表喘先，可以讓其中一個(gè)變量遍歷的速度快一些，比如一次走兩步廷粒，或者是走若干步窘拯。我們?cè)谟龅竭@類面試的時(shí)候，千萬(wàn)不要自亂陣腳坝茎，學(xué)會(huì)理性分析問(wèn)題涤姊。
原本是想給我的小伙伴說(shuō)再見(jiàn)了，但唯恐大家還沒(méi)學(xué)到真本事嗤放，所以在這里再留一個(gè)拓展題思喊。
面試題：給定一個(gè)單鏈表的頭結(jié)點(diǎn)，刪除倒數(shù)第 k 個(gè)結(jié)點(diǎn)次酌。
哈哈恨课，和上面的題目?jī)H僅只是把獲得它的值變成了刪除舆乔，不少小伙伴肯定都偷著樂(lè)了，但南塵還是先提醒大家剂公，不要太得意忘形喲~
好啦希俩，咱們明天再見(jiàn)啦~
