ARTS leetcode7 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
           

题目意思：合并两个有序链表，形成一个新的链表，合成以后的链表也是有序的。

看到这个题的时候，想起了大学上数据结构的时候，学习链表知识的第一个例子就是合并两个有序链表，当时是c语言写的，两种形式，一种是用递归，一种是不用递归，我这里采用了递归的方法。

思路：

（1）方法的参数是两个listNode对象，判断是否为空，如果全为null,则返回null，结束；

如果l1为null,则返回l2;如果l2为null，则返回l1；

（2）将两个链表的第一个元素做比较，如果l1的第一个节点值小于l2的第一个节点值，那么就把l1赋值给新创建的node对象，

然后node对象的下一个节点就递归调用方法，第一个参数就是l1.next，第二个参数l2

（3）将两个链表的第一个元素做比较，如果l1的第一个节点值大于或等于l2的第一个节点值，那么就把l2赋值给新创建的node对象，

然后node对象的下一个节点就递归调用方法，第一个参数就是l1，第二个参数l2.next

举个例子来说一下，(2)(3)中传参的含义：就用上面的demo来说，1和1相比较，走(3)，l2的第一个被赋值到node，然后我们需要做的就是将l2的next然后继续与l1的一个相比较，所以传参就是这个意思。

代码实现（递归形式）:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode node;
        if(l1 == null && l2 == null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val<l2.val){
            node = l1;
            node.next = mergeTwoLists(l1.next,l2);
        }else {
            node = l2;
             node.next = mergeTwoLists(l1,l2.next);
        }
        return node;
    }
}
           

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 37 MB, less than 97.90% of Java online submissions for Merge Two Sorted Lists.
           

code2:非递归的形式，利用循环，代码实现如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //首先的初始化一个node
        ListNode result = new ListNode(0);
        ListNode node = result;
        //两个node都不为空的情况下循环
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                node.next = l1;
                l1 = l1.next;
            }else {
                node.next = l2;
                 l2 = l2.next;
            }
            node = node.next;
        }
        //这里主要是为了两个链表长度不一样的时候，所采取的处理方法。
        if(l1!=null){
            node.next = l1;
        }
        if(l2!=null){
            node.next = l2;
        }
        //因为初始化的时候给链表多一个节点0，所以只需要0以后的节点就ok
        return result.next;
    }
}
           

Runtime: 1 ms, faster than 99.55% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 36.8 MB, less than 98.00% of Java online submissions for Merge Two Sorted Lists.
           

继续看另外一种实现，是在leetcode discuss中看到的一个大佬写的，代码实现很简洁，并没有创建新的ListNode对象，但是他缺了一种考虑，就是如果两个链表都是空的情况下，应该返回null(个人理解)。他也采用了递归的形式进行调用，但是存在一个问题，题目说了需要返回一个new List来存储合并后的list的值，但是这个大佬的写法是改变了原有链表的值，在没有重新创建list的情况下，也实现了，感觉和题目要求有点背离，但是居然也跑成功了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
		if(l2 == null) return l1;
		if(l1.val < l2.val){
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		} else{
			l2.next = mergeTwoLists(l1, l2.next);
			return l2;
		}
    }
}
           

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 37.1 MB, less than 97.90% of Java online submissions for Merge Two Sorted Lists.