ARTS leetcode7 Merge Two Sorted Lists

本文主要是介绍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;}//首先的初始化一个nodeListNode 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以后的节点就okreturn 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.

这篇关于ARTS leetcode7 Merge Two Sorted Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---