題目描述

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

示例：輸入{1,3,5},{2,4,6}返回值{1,2,3,4,5,6}

描述

這是一篇針對初學者的題解，共用2種方法解決。

知識點：單鏈表，遞歸

難度：一星

題解：

題目要求：給兩個非遞減單鏈表l1, l2，合并為一個非遞減的單鏈表。

方法一：迭代版本求解

初始化：定義cur指向新鏈表的頭結點

操作：

如果l1指向的結點值小于等于l2指向的結點值，則將l1指向的結點值鏈接到cur的next指針，然后l1指向下一個結點值

否則，讓l2指向下一個結點值

循環(huán)步驟1,2，直到l1或者l2為nullptr

將l1或者l2剩下的部分鏈接到cur的后面

技巧

一般創(chuàng)建單鏈表，都會設一個虛擬頭結點，也叫哨兵，因為這樣每一個結點都有一個前驅結點。

時間復雜度：O(m+n),m，n分別為兩個單鏈表的長度

空間復雜度：O(1)

方法二：遞歸版本

方法一的迭代版本，很好理解，代碼也好寫。但是有必要介紹一下遞歸版本，可以練習遞歸代碼。

寫遞歸代碼，最重要的要明白遞歸函數的功能?？梢圆槐仃P心遞歸函數的具體實現(xiàn)。

比如這個ListNode* Merge(ListNode* pHead1, ListNode* pHead2)

函數功能：合并兩個單鏈表，返回兩個單鏈表頭結點值小的那個節(jié)點。

如果知道了這個函數功能，那么接下來需要考慮2個問題：

遞歸函數結束的條件是什么？

遞歸函數一定是縮小遞歸區(qū)間的，那么下一步的遞歸區(qū)間是什么？

對于問題1.對于鏈表就是，如果為空，返回什么

對于問題2，跟迭代方法中的一樣，如果PHead1的所指節(jié)點值小于等于pHead2所指的結點值，那么phead1后續(xù)節(jié)點和pHead節(jié)點繼續(xù)遞歸

時間復雜度：O(m+n)

空間復雜度：O(m+n),每一次遞歸，遞歸棧都會保存一個變量，最差情況會保存(m+n)個變量