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