JZ014-合并兩個排序的鏈表

題目描述

題目：輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規(guī)則。

示例：

輸入

node1: 1 -> 3 -> 5 -> 7 -> 9 

node2: 2 -> 4 -> 6 -> 8 -> 10

輸出

result  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

解析思路

鏈表是由一系列連接在一起的結點構成，其中的每個結點都是一個數據結構。

         

        這道題屬于鏈表題型中等題目，做法很簡單 ,大致思路如下：

第一種方法：常規(guī)方法，

      ①創(chuàng)建新的鏈表頭pre，用于存儲result鏈表

      ②兩個鏈表同時遍歷，按照下圖所示進行連接鏈表

      ③返回pre鏈表頭，此時pre就是合并好的新鏈表

第二種方法：遞歸，寫遞歸的代碼很簡單，最重要的要明白遞歸函數的功能。可以不必關心遞歸函數的具體實現。
比如這個ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函數功能：合并兩個單鏈表，返回兩個單鏈表頭結點值小的那個節(jié)點。

代碼Code

方法一：

方法二：

心得體會

       思考為什么他可以寫出這么好的代碼，把每道題的思路理解后用筆記本記錄下來，爭取刷到融會貫通，即看見有個題能自動歸類到某個方面，這樣有一定好處。面試最重要的是讓面試官日后能愿意與你以后一起工作，因此溝通交流非常重要。比如有時候面試需要交流，看著像是一道排序的題做不出來，就可以跟面試官交流：“我有幾個不成熟的想法，一排序，二動態(tài)規(guī)劃，三是直接搜索算法”，面試官可能就給個提示：“你先用排序試試吧“。

end

往期推薦

• JZ015-反轉鏈表

• JZ014-鏈表中倒數第k個結點

• JZ003-從尾到頭打印鏈表