主題
題目連結(jié)：
題目意譯：
給定一個連結(jié)串列（Linked List）的開頭節(jié)點 head，在串列中每一個節(jié)點包含著一個整數(shù)值。
請在每一對相鄰節(jié)點對之間插入一個新的節(jié)點，並使得其節(jié)點值等於該節(jié)點對兩者的數(shù)值之最大公因數(shù)。
回傳插入節(jié)點後的連結(jié)串列。
兩個數(shù)字的最大公因數(shù)為可以同時整除這兩個數(shù)字的最大正整數(shù)。
限制：
串列中的節(jié)點數(shù)位於範(fàn)圍 [1, 5000] 中。
1 ≦ Node.val ≦ 1000
範(fàn)例測資：
範(fàn)例 1：
輸入： head = [18,6,10,3]
輸出： [18,6,6,2,10,1,3]
解釋： 上面的示意圖代表著原始的串列，下面的示意圖則是插入新節(jié)點後的串列（藍(lán)色節(jié)點為插入的節(jié)點）。
- 我們插入在第 1 、 2 個節(jié)點中間插入 18 和 6 的最大公因數(shù) = 6 進(jìn)去。
- 我們插入在第 2 、 3 個節(jié)點中間插入 6 和 10 的最大公因數(shù) = 2 進(jìn)去。
- 我們插入在第 3 、 4 個節(jié)點中間插入 10 和 3 的最大公因數(shù) = 1 進(jìn)去。
沒有更多相鄰的節(jié)點存在了，所以我們回傳現(xiàn)在的連結(jié)串列。
範(fàn)例 2：
輸入： head = [7]
輸出： [7]
解釋： 上面的示意圖代表著原始的串列，下面的示意圖則是插入新節(jié)點後的串列。
沒有相鄰的節(jié)點，所以回傳原始的連結(jié)串列即可。
解題思維：
沒什麼特別的。就單純地掃過一次串列找到每一個節(jié)點對 (x, y)，然後建立一個新的節(jié)點 z，其值為 x 、 y 兩個節(jié)點值的最大公因數(shù)（使用輾轉(zhuǎn)相除法，參見維基頁面）。接著令 x 的下一個節(jié)點指向 z，然後讓 z 的下一個節(jié)點指向 y 即可完成插入 z 的動作。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
