LeetCode 021 Merge Two Sorted Lists

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

题目分析

题目很简单就是将两个有序的链表合并成一个，这个题目很简单，但我写的时候犯了很多的小错误。循环的边界总是判断不准，应该使用l1 != null用的是 l1.next != null，导致一直少一个值。

一开始我每次都新建一个节点，然后给她赋值。

/*** 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;ListNode list = new ListNode(0);ListNode listNode = list;while (l1 != null &&l2 != null){
    if(l1.val>l2.val){
    list.val =l2.val;l2 = l2.next;}else {
    list.val = l1.val;l1 = l1.next;}if(l1 != null && l2!= null){
    list.next = new ListNode(0);list = list.next;}}//经过上面的循环出来肯定有一个已经到了最后，而还有一个至少剩一个节点if(l1 ==null)list.next = l2;elselist.next = l1;return listNode;}
}

运行时间有待提升。不在创建新的节点，而是直接链接到原来的链表上获取值。

/*** 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 list = new ListNode(0);ListNode listNode = list;while (l1 != null &&l2 != null){
    //设置初始结点当队头，直接在后面链接正确的值，返回时应返回链头的nextif(l1.val>l2.val){
    list.next =l2;l2 = l2.next;list = list.next;}else {
    list.next = l1;l1 = l1.next;list = list.next;}          }if(l1 !=null)list.next = l1;elselist.next = l2;return listNode.next;}
}

虽然运行时间上来了，但是使用的内存大大增加，我的理解是每次都是一个长的链表链接在已排好序的链表后面，这样内存中每次都会预存后面的节点信息，增加了内存消耗。不知道理解是否正确，若是有啥不对的，或者是指教的话，欢迎评论告诉我。