leetcode-合并两个排序的链表

刷leetcode第二十五题"合并两个排序的链表"，以下为解题过程

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题目解析

1. 使用迭代，新建链表，每一个进行比较，将小的那个进行拼接到新链表中。

2. 使用递归。递归中注意新节点的拼接以及条件跳出

注意

1. 因为两个链表的长度不一定为一样，最后要把剩余的节点拼接到新链表中。
2. 在迭代中，需要一个备份将此链表的地址保存，以免在后面进行覆盖修改。
3. 在递归中，cur链表需要新建，next也需要赋值修改。

具体代码实现

迭代方法

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
        return null;
    }

    if (l1 == null) {
        // 两者有一为空
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    //cur 和 node 引用指向某节点，但 cur 和 dum 是两个独立变量，保存此节点的地址。当改变 cur， dum仍然指向这个节点，所以没有变化
    ListNode node = new ListNode(0), cur = node;
    // l1和l2不为空的时候
    while (l1 != null && l2 != null) {
        // 比较l1和l2的值
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    // 因为两个链表的长度不一样，所以要截取剩下的
    cur.next = l1 != null ? l1 : l2;
    return node.next;
}

递归方法

public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
    // 使用递归思想
    if (l1 == null && l2 == null) {
        return null;
    }
    if (l1 == null) {
        // 两者有一为空
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    // 新建节点
    ListNode cur = null;
    if (l1.val >= l2.val) {
        cur = new ListNode(l2.val);
        cur.next = mergeTwoLists2(l1, l2.next);
    } else {
        cur = new ListNode(l1.val);
        cur.next = mergeTwoLists2(l1.next, l2);
    }
    return cur;
}