什么是合并兩個有序鏈表
假設(shè)有兩條鏈表棍潘，這兩條鏈表分別都是升序排列的恃鞋，如下圖所示：
現(xiàn)在要求將二者合并成一條鏈表，并且該鏈表也是升序排列的亦歉，合并后的鏈表如下圖所示：
思路
如果對歸并排序有所了解山宾，那么這個問題就很簡單。在歸并排序的遞歸過程中鳍徽，我們的算法是將原始數(shù)組a切割成兩段：a1和a2资锰，對a1和a2分別排序后，再將二者歸并成一個有序的數(shù)組阶祭。這里的思路是一樣的绷杜，只不過將數(shù)組變成了鏈表。
大體的思路是：
- 確定合并后的新鏈表的頭節(jié)點
head - 使用一個指針
l3濒募，初始化為head鞭盟，用這個指針來組織新鏈表的各個節(jié)點 - 使用兩個指針
l1和l2，分別初始化為兩條原始鏈表的頭節(jié)點瑰剃，用來遍歷這兩條鏈表齿诉。 - 當
l1的值小于等于l2的值時，那么令l3->next=l1晌姚，否則令l3->next=l2 - 一般情況下粤剧，有一個鏈表會提前遍歷結(jié)束，例如鏈表1首先遍歷結(jié)束挥唠，也就是
l1=Null時抵恋，那么由于另一條鏈表本身就是有序的，此時直接令l3->next=l2宝磨，就可以完成合并操作了弧关。
哨兵方法簡化代碼
如果直接按上述思路編碼盅安，那么確定新鏈表的頭節(jié)點head需要編寫額外的代碼。但仔細想想世囊，確定新鏈表head的過程無非是比較l1 head和l2 head的值别瞭，將其中較小值的那個節(jié)點作為新鏈表的head，這個操作和后續(xù)遍歷兩條鏈表的比較操作的邏輯是一致的株憾。為了避免這種冗余代碼（以及處理各種邊界問題）蝙寨，可以考慮一種哨兵方法。也就是号胚，虛擬一個節(jié)點prehead籽慢，認為它的下一個節(jié)點就是新鏈表的頭節(jié)點head，并讓l3=prehead猫胁，從這個虛擬節(jié)點開始組織新的鏈表箱亿，這樣就無需對確定頭節(jié)點的操作做特殊處理了。在最后整理好新的鏈表時弃秆，我們直接返回prehead->next届惋，得到的自然就是l3的頭節(jié)點了。
代碼實現(xiàn)
下面給出Python代碼的一個實現(xiàn)：
class Solution:
def mergeTwoLists(self, l1, l2):
# 新建一個虛擬節(jié)點作為哨兵節(jié)點
# 作為目標鏈表l3頭節(jié)點的前面一個節(jié)點
prehead = ListNode(-1)
# 利用prev節(jié)點來組織新的鏈表
prev = prehead
# 循環(huán)截至條件是l1和l2其中任意一個鏈表已經(jīng)遍歷完
while l1 and l2:
# 比較l1和l2指向的節(jié)點的值
# 將值比較小的那個加入到新鏈表中
# 然后將該鏈表過渡到下一個節(jié)點
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# 將還沒有遍歷完的那個鏈表直接添加到新鏈表的末尾
prev.next = l1 if l1 is not None else l2
# 返回的是哨兵節(jié)點的下一個節(jié)點菠赚，也就是新鏈表的頭節(jié)點
return prehead.next
