21. 合并两个有序链表

解题思路

解法1：

1.遍历两个有序链表，结束条件为L1、L2都为null
2.对每次遍历到的数据做判断，区分三种情况：
1）L1、L2都不为空--判断此时两个val的大小，创建node
2）L1不为空、L2为空--用L1的val创建node
3）L1为空、L2不为空--用L2的val创建node
3.创建链表的过程中，需要注意，头结点为空时，需要先创建头结点

解法2

1.巧妙运用哑结点的技巧，解决头结点为空的问题
2.将哑结点的链表初始化为L1
3.遍历L2，找到哑结点所在链表合适位置，插入数据
4.返回哑结点的next即为ans

解题遇到的问题

1.创建链表的过程中，需要注意，头结点为空时，需要先创建头结点

后续需要总结学习的知识点

1.链表的遍历、插入、删除、添加，自己通过java代码实现

##解法1
class Solution {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = null;
        ListNode head = result;
        while (l1 != null || l2 != null) {
            int val = 0;
            if (l1 != null && l2 != null) {
                if (l1.val > l2.val) {
                    val = l2.val;
                    l2 = l2.next;
                } else {
                    val = l1.val;
                    l1 = l1.next;
                }
            } else if (l1 == null && l2 != null) {
                val = l2.val;
                l2 = l2.next;
            } else if (l2 == null && l1 != null) {
                val = l1.val;
                l1 = l1.next;
            }

            if (head == null) {
                result = new ListNode(val);
                head = result;
            } else {
                ListNode temp = new ListNode(val);
                result.next = temp;
                result = result.next;
            }
        }
        return head;
    }
}

##解法2
class Solution {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode ans = node;
        node.next = l1;
        ListNode pre = node;
        node = node.next;
        while (l2 != null) {
            while (node != null) {
                if (node.val >= l2.val) {
                    break;
                }
                pre = node;
                node = node.next;
            }
            if (node != null) {
                ListNode temp = new ListNode(l2.val);
                temp.next = pre.next;
                pre.next = temp;
            } else {
                pre.next = new ListNode(l2.val);
            }
            pre = pre.next;
            l2 = l2.next;
        }
        return ans.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}