算法

(二路歸并) O(n)

新建頭部的保護(hù)結(jié)點(diǎn)s，設(shè)置p指針指向s。

若當(dāng)前l(fā)1指針指向的結(jié)點(diǎn)的值val比l2指針指向的結(jié)點(diǎn)的值val小，則令p的next指針指向l1，且l1后移；否則指向l2，且l2后移。

然后p指針按照上一部設(shè)置好的位置后移。

循環(huán)以上步驟直到l1或l2為空。

將剩余的l1或l2接到p指針后邊。

時(shí)間復(fù)雜度

兩個(gè)鏈表各遍歷一次，所以時(shí)間復(fù)雜度為O(n)