leetcode 21.合并两个有序链表

leetcode 21.合并两个有序链表

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

迭代法：

思路： 不断迭代，谁小指向谁

   public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1== null) {
            return list2;
        }
        if (list2== null) {
            return list1;
        }
        //虚拟节点/哨兵节点，后面会指向合并后的链表。可以更容易地返回合并后的链表
        ListNode prehead = new ListNode(-1);
        ListNode listNode = prehead;

        //遍历，谁小指向谁
        while (list1!=null && list2!=null) {
            if (list1.val < list2.val) {
                listNode.next = list1;
                //向后迭代
                list1 = list1.next;
            } else {
                listNode.next = list2;
                list2 = list2.next;
            }
            //向后迭代
            listNode = listNode.next;
        } 
        //一个链表遍历完了，另外一个链表还有未合并完的部分，也要合并进结果里面。
        if (list1 == null) {
            listNode.next = list2;    
        } else {
            listNode.next = list1;    
        }

        return prehead.next;
}

递归法

思路： 判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
           //自顶向下。
           //由于 l1的节点值比较小，所以需要合并到结果集中。
           // l1指向的next 节点是合并后的节点，l1.next 和 l2 是下一次参与递归的节点
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }