美文网首页
面试题17:合并两个排序的链表(剑指offer)

面试题17:合并两个排序的链表(剑指offer)

作者: 辉辉_teresa | 来源:发表于2021-02-28 21:03 被阅读0次

    题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图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;
        }
    }
    

    相关文章

      网友评论

          本文标题:面试题17:合并两个排序的链表(剑指offer)

          本文链接:https://www.haomeiwen.com/subject/ntenfltx.html