ARTS leetcode7 Merge Two Sorted Lists

古城微笑少年丶 2022-02-05 01:13 113阅读 0赞

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的一个相比较，所以传参就是这个意思。

代码实现（递归形式）:

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.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220205/6787602b6b744562bf32909e83112bb6.png