鏈表面試題3：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成 的。

首先我們的思想是將得一個鏈表和第二個鏈表的每個結點進行比較，誰小誰就插入到新鏈表的最后。

首先我們要判段鏈表是否為空，如果為空的話，就返回NULL，再這里如果第一個為空，就返回第二個，如果第二個為空就返回第一個，如果都為空，隨便返回一個都是NULL。采用尾插法，用兩個指針，一個指頭，一個指尾。

總體循環，當兩個鏈表都不為空的時候，判斷第一個鏈表的第一個結點的值是否比第二個結點的小，如果小，則需要判斷當前鏈表中有沒有結點，如果沒有，則直接插入，否則，插入后，移動尾指針。同時，并讓n1走到下一個結點。反過來也是如此，只不過如果n2小，就讓n2走到下一個結點，n1不動。仔細體會。

如果其中有一個鏈表已經走完，則直接將沒走完的鏈表接到后面就可以。