[劍指Offer] 第3章課後題詳解[劍指Offer] 第3章課後題詳解

<a href="#%e5%89%91%e6%8c%87offer-%e7%ac%ac3%e7%ab%a0%e8%af%be%e5%90%8e%e9%a2%98%e8%af%a6%e8%a7%a3">劍指offer 第3章課後題詳解</a>

<a href="#%e7%9b%ae%e5%bd%95">目錄</a>

<a href="#%e5%a4%a7%e6%95%b0%e5%8a%a0%e6%b3%95">大數加法</a>

<a href="#%e5%88%86%e6%9e%90">分析</a>

<a href="#%e8%a7%a3%e6%b3%95">解法</a>

<a href="#%e4%bc%98%e5%8c%96">優化</a>

<a href="#%e9%93%be%e8%a1%a8%e7%9a%84%e4%b8%ad%e9%97%b4%e8%8a%82%e7%82%b9">連結清單的中間節點</a>

<a href="#%e5%88%86%e6%9e%90-1">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-1">解法</a>

<a href="#%e7%8e%af%e5%bd%a2%e9%93%be%e8%a1%a8">環形連結清單</a>

<a href="#%e5%88%86%e6%9e%90-2">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-2">解法</a>

<a href="#%e5%8f%8d%e8%bd%ac%e9%93%be%e8%a1%a8">反轉連結清單</a>

<a href="#%e5%88%86%e6%9e%90-3">分析</a>

<a href="#%e8%a7%a3%e6%b3%95-3">解法</a>

本題為《劍指offer》“面試題12：列印1到最大的n位數”一節中的“相關題目”。

定義一個函數，在該函數中可以實作任意兩個整數的加法。

由于沒有限定輸入兩個數的大小範圍，是以需要把它當做大數問題來處理。大數無法用int，long甚至long long類型來表示，這裡選擇用字元串來表示。這裡需要注意的一個點是，沒有限制不能輸入負數，還得考慮負數的情況。由于負數的加入，我們需要考慮，運算到底是做加法還是做減法，最後結果的符号問題。

本解法還有兩個地方可以進一步優化：

2.在compute函數中，做了兩步運算，第一步為s1低位與s2的運算，第二步是s1高位與s2最高位進位或退位的運算，這裡可以再提取一個函數出來，用于計算兩個相等長度字元串的運算，接收4個參數，分别為2個加數的引用、進位标志和運算類型，傳回最高位進位标志，然後調用兩次，第一次是s1低位與s2的運算，第二次是s1高位與全為’0’的字元串的運算。這樣可以讓代碼更簡潔，提升代碼的拓展性。

本題為《劍指offer》“面試題15：連結清單中倒數第k個結點”一節中的“相關題目”。

求連結清單的中間結點，如果連結清單中的結點總數為奇數，傳回中間結點；如果結點總數為偶數，傳回中間兩個結點的任意一個。連結清單節點定義如下：

可以定義兩個指針，一個每次走兩步，一個每次走一步，走兩步的指針抵達連結清單尾部時，則走一步的指針正好在連結清單中間。需要注意的是空連結清單的情況，且走兩步的指針不能連續走兩步，每走一步都必須判定是否已達到連結清單尾部。

判斷一個單向連結清單是否形成了環形結構。連結清單節點定義如下：

與上道題類似，定義兩個指針，走兩步的指針如果能追到走一步的指針，則形成了環形結構，如果走到底了，則沒有形成環形結構。同樣注意的也是空連結清單的處理和走兩步之間的判定。

本題為《劍指offer》“面試題16：反轉連結清單”一節中的“本題拓展”。

定義一個函數，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點，用遞歸的方式實作。連結清單節點定義如下：

資料結構中連結清單插入有兩種方法，頭插法和尾插法，尾插法是連結清單尾部最後一個節點的next指針指向插入節點，頭插法是用插入節點的next指針指向連結清單的第一個節點（非固定頭節點的情況）。将連結清單中的節點依次用頭插法的方式插入到一個新的空連結清單中則可以實作連結清單的反轉。這裡需要注意的是輸傳入連結表為空，輸傳入連結表隻有一個節點的特例，以及連結清單斷裂的防止。