面试题17：合并两个排序的链表（剑指offer）

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图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 的头结点的值小于链表2 的头结点的值，因此链表1的头结点是合并后链表的头结点。（b）在剩余的结点中，链表2 的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余结点的头结点，把这个结点和之前已经合并好的链表的尾结点链接起来。

2.自己先写的（循环感脚也挺好的，就是代码有点长）

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;
    }
}