最多連續(xù)數(shù)的子集及單鏈表和之戀分析及解答
給一個整數(shù)數(shù)組， 找到其中包含最多連續(xù)數(shù)的子集，比如給：15, 7, 12, 6, 14, 13, 9, 11，則返回: 5:[11, 12, 13, 14, 15] 。
最簡單的方法是sort然后scan一遍，但是要 o(nlgn) ， 有什么 O(n) 的方法嗎？
單鏈表和之戀分析：
原題：兩個單鏈表（singly linked list），每一個節(jié)點(diǎn)里面一個0-9的數(shù)字，輸入就相當(dāng)于兩個大數(shù)了。然后返回這兩個數(shù)的和（一個新list）。這兩個輸入的list長度相等。 要求是：
- 不用遞歸；
- 要求算法在最好的情況下，只遍歷兩個list一次 ，最差的情況下兩遍。
分析：遇到一個面試題，#首先，要澄清和理解題意，確保你的理解和面試官的本意一致。#題中的單鏈表，可不可以原地修改？是從高位到低位，還是 低位到高位？如果是從低位到高位，那么問題很簡單，是不是？只要兩個指針移動（因?yàn)槭堑乳L的），對應(yīng)位置相加，同時記錄是否有進(jìn)位，產(chǎn)生的結(jié)果存入新的鏈 表中。
如果是從高到低，問題就復(fù)雜了，進(jìn)位是萬惡之源。這時，也許我們會想到reverse兩個單鏈表（其實(shí)，這也是一道很好的面試題，如何做？考慮遞歸和遞推兩種算法），但這樣做，是不是最好最壞情形都得遍歷兩次？好像不合題意。
如果新的鏈表的節(jié)點(diǎn)可以存一個或兩個數(shù)字，那么，第一遍，將相應(yīng)節(jié)點(diǎn)的數(shù)字相加，存入新的鏈表，并用一個flag標(biāo)志整個操作中是否有進(jìn)位。如果沒 有，結(jié)了；否則，再掃描一遍新的鏈表，將有兩個數(shù)字的進(jìn)位存到上一個節(jié)點(diǎn)。如果新的鏈表是雙的，問題比較簡單；如果新的鏈表還是單的，這一步也會很復(fù)雜， 比如，１０－〉９－〉９－〉１２，如何轉(zhuǎn)成１－〉１－〉０－〉０－〉２，本身也是一個很好的面試題。這時可能需要reverse鏈表再操作。
如果新的鏈表的節(jié)點(diǎn)只能存一個數(shù)字，那么能有什么辦法？
也許你有更好的解決辦法？期待。
面試題單鏈表和之戀精美解答
本期推薦Hawstein （新浪微博@Hawstein）對于面試題求兩個單鏈表的和的精美分析和解答。如果你對我們的面試題有不同的更優(yōu)的解答，請回復(fù)我們。對于耳目一新的深思熟慮的分析和解答，我們將在此推薦。
今天的 Bonus 面試題：一個單鏈表head，和一個指向表中某個節(jié)點(diǎn)的指針p，怎么以最快的速度刪除指針p所指的節(jié)點(diǎn)？
題目
兩個單鏈表（singly linked list），每一個節(jié)點(diǎn)里面一個0-9的數(shù)字， 輸入就相當(dāng)于兩個大數(shù)了。然后返回這兩個數(shù)的和（一個新list）。這兩個輸入的list 長度相等。 要求是：
- 不用遞歸。
- 要求算法在最好的情況下，只遍歷兩個list一次， 最差的情況下兩遍。
解答
這是陳利人同學(xué)今天發(fā)在待字閨中的面試編程題目，看了一下解答， 發(fā)現(xiàn)要么需要遍歷鏈表兩次，要么需要額外的存儲空間，難道就沒有更優(yōu)的解法了嗎？ 想了一下，發(fā)現(xiàn)還是有的。
OK，我們把這個問題具體化一下吧：(這里就不再考慮從低到高存等blabla情況)
兩個單鏈表，每個節(jié)點(diǎn)存儲一個0-9的數(shù)字，那么一個單鏈表就表示一個大數(shù)。 從高位到低位存，即表頭對應(yīng)的是這個大數(shù)的最高位。兩個鏈表的長度相等， 我們要返回一個新的單鏈表，是這兩個輸入鏈表代表的數(shù)的和。我們不能使用遞歸， 不能使用額外的存儲空間，即空間復(fù)雜度是O(1)。只遍歷輸入鏈表一次， 輸出鏈表也是單鏈表(沒有前向指針)。
既然只能遍歷兩個輸入鏈表一次，那我們就從高位加起唄。在這種限制條件下， 這是唯一的出路。然后呢？進(jìn)位咋整？先加高位，再加低位， 低位產(chǎn)生的進(jìn)位怎么加到高位去？我們可沒有前向指針哦親。既然沒有前向指針， 我們就讓一個臨時指針指向高位，當(dāng)?shù)臀幌嗉赢a(chǎn)生進(jìn)位時，我們就可以操作高位了。 讓我們看看圖示：
- 輸入鏈表1： 1 2 3
- 輸入鏈表2： 1 2 8
- 輸出鏈表： 2 4
- 兩個指針： p q
當(dāng)指向輸出鏈表當(dāng)前結(jié)點(diǎn)的指針q發(fā)現(xiàn)3+8=11，產(chǎn)生進(jìn)位，指向高位的p就將結(jié)點(diǎn)值加1。 注意，兩個0-9的數(shù)相加，要么不進(jìn)位，要么進(jìn)位為1，只有兩種情況。因此， 我們不用考慮進(jìn)位是其它數(shù)，這一點(diǎn)很重要，后面會看到的。
這樣就OK了嗎？當(dāng)然不是，如果你遇上連續(xù)進(jìn)位，怎么破？請看下面的情況：
- 輸入鏈表1： 1 2 3 4 5
- 輸入鏈表2： 1 7 6 5 9
顯然，指向高位的指針p總是緊跟著指向當(dāng)前結(jié)點(diǎn)的指針q是不行的， 這樣當(dāng)遇上連續(xù)進(jìn)位時，比p更高位的位也需要改變。既然p不能緊跟著q， 我們就不讓它們緊挨著，給它們產(chǎn)生點(diǎn)距離?？紤]一下，什么情況下會產(chǎn)生連續(xù)進(jìn)位？ 9! 嗯，遇上9的時候。它要連續(xù)進(jìn)位到哪一位？不為9的那一位。因此，指針p 要停留在和不為9的那一位上，看圖示：
- 輸入鏈表1： 1 2 3 4 5
- 輸入鏈表2： 1 7 6 5 9
- 輸出鏈表： 2 9 9 9
- 兩個指針： p q
這回當(dāng)q發(fā)現(xiàn)，需要進(jìn)位了，只需要把p所指結(jié)點(diǎn)加1，然后把p，q間的結(jié)點(diǎn)都置0即可。 為什么都置0了呢，因?yàn)檫M(jìn)位只可能是1，9+1=10，留在該位的自然是0了。
分析完畢，這種方法在任何時候都只需要遍歷輸入鏈表一次，空間復(fù)雜度O(1)。
