2019年5月13日

目录

题目

解决方法一：

性能结果：

小结：

解决方法二：

性能结果：

思路：

小结：

前言：基础不好的童鞋，花点时间回顾下基础数据结构：链表

题目

解决方法一：

package leetCode;

/**
 * Date: 2019/5/8 12 :21
 *
 * @todo 将两个有序链表合并为一个新的有序链表并返回。
 */

public class MergeTwoOrderedLists {
    public static void main(String[] args){
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next= new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next=new ListNode(3);
        l2.next.next= new ListNode(4);
        System.out.println("l1="+l1+"  l2="+l2);
        ListNode l3 = mergeTwoLists(l1, l2);
        System.out.println("l3="+l3);

    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 1.l3取l1的首结点
        ListNode head = new ListNode(0);
        ListNode cur = head;

        if(l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }

        if (l1 != null && l2 != null){


            // 2.l2或者l1的结点都不为空
            while (l2 != null || l1 != null){

                if (l1.val < l2.val){
                    cur.next = l1;  //l1首元素地址赋值给cur指向的next元素
                    cur = cur.next; //cur也指向next元素
                    l1 = l1.next;
                }else {
                    cur.next = l2;
                    cur = cur.next;
                    l2 = l2.next;
                }

                // 3.任意一条链表为空时，直接连接另外一条即可
                if (l1 == null){
                    cur.next = l2;
                    break;
                }

                if (l2 == null){
                    cur.next = l1;
                    break;
                }
            }

        }

        return head.next;
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    public ListNode() {
    }
};

性能结果：

小结：

• 链表保存的下一个节点信息，是下一个元素的内存首地址，为null时则是链表的最后一个元素；
• 新建头结点，新建cur为位移指针，cur的作用是作为新建头结点的指针，不断给头结点进行元素补充；
• 每个方法都要考虑充分的异常情况：比如某个链表为空，那就返回另外一个；比如两个输入链表的长度不一致，也要考虑；

解决方法二：

/**
 * 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;
        }
    }
}

性能结果：

思路：

1）迭代方法

每次选两个链表头结点最小的，比如：我们生活中，有两个已经按照高矮排好的队伍，我们如何把变成一个队伍！当然，每次选两个队伍排头的，比较他们的高矮!组成新的的队伍。

时间复杂度：O(m+n)O(m+n)

空间复杂度：O(m+n)O(m+n)

2）递归方法

小结：

从大脑反应程度看，确实灵敏了很多，自己也看到了进步，but，远远不够的，因为《数据结构与算法》一书，才刚刚开始看啊！没到登峰造极，剑不能收！努力。