題目：輸入兩個遞增排序的鏈表钱烟，合并這兩個鏈表并使新鏈表中的結(jié)點仍然是按照遞增排序的绅作。例如輸入圖3.7中的鏈表1和鏈表2魁蒜，則合并之后的升序鏈表如鏈表3所示憔恳。
微信圖片_20210228203527.jpg
1.劍指offer書中的代碼（遞歸）
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null) return l2;
else if (l2 == null) return l1;
ListNode pMergedHead = null;
if (l1.val < l2.val)
{
pMergedHead = l1;
pMergedHead.next = MergeTwoLists(l1.next, l2);
}
else
{
pMergedHead = l2;
pMergedHead.next = MergeTwoLists(l1, l2.next);
}
return pMergedHead;
}
（a）鏈表1 的頭結(jié)點的值小于鏈表2 的頭結(jié)點的值，因此鏈表1的頭結(jié)點是合并后鏈表的頭結(jié)點挥转。（b）在剩余的結(jié)點中海蔽，鏈表2 的頭結(jié)點的值小于鏈表1的頭結(jié)點的值共屈，因此鏈表2的頭結(jié)點是剩余結(jié)點的頭結(jié)點，把這個結(jié)點和之前已經(jīng)合并好的鏈表的尾結(jié)點鏈接起來党窜。
2.自己先寫的（循環(huán)感腳也挺好的拗引，就是代碼有點長）
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode newHead = null;
if (l1.val > l2.val)
{
newHead = l2;
l2 = l2.next;
}
else
{
newHead = l1;
l1 = l1.next;
}
var tempHead = newHead;
while (l1!=null && l2!=null)
{
if (l1.val > l2.val)
{
tempHead.next = l2;
l2 = l2.next;
}
else
{
tempHead.next = l1;
l1 = l1.next;
}
tempHead = tempHead.next;
}
if (l1 != null)
tempHead.next = l1;
if (l2 != null)
tempHead.next = l2;
return newHead;
}
鏈表
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int x)
{
val = x;
}
}
