算法小练——合并两个有序链表

title: 算法小练——合并有序链表
categories:

• Algorithms
  tags:
• esay
  abbrlink: 2086973647
  date: 2019-11-06 20:25:24

合并两个有序链表

描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

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

代码

public class Solution {
    ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode ans = new ListNode(0);
        if(l1==null){
            return l2;
        }
        if(l2 ==null){
            return l1;
        }
        while (true){
            if(l1==null){
                ListNode temp = ans;
                while (temp.next!=null){
                    temp =temp.next;
                }
                temp.next = l2;
                return ans.next;
            }
            if(l2==null){
                ListNode temp = ans;
                while (temp.next!=null){
                    temp =temp.next;
                }
                temp.next = l1;
                return ans.next;
            }
            int c =Math.min(l1.val,l2.val);
            ListNode temp = ans;
            while (temp.next!=null){
                temp =temp.next;
            }
            temp.next = new ListNode(c);
            if(c==l1.val){
                l1 =l1.next;
            }else {
                l2 =l2.next;
            }

        }

    }

}

笔记

效率很低

代码优化

//递归
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

//迭代
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // maintain an unchanging reference to node ahead of the return node.
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // exactly one of l1 and l2 can be non-null at this point, so connect
        // the non-null list to the end of the merged list.
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}