思路受到了些许阻碍，先写写算法，找找状态吧

第三题（简单）合并两个有序链表

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

目的：获得一个新的升序链表

1 -> 3 -> 5 + 2 -> 4 -> 6 = 1 -> 2 -> 3 -> 4 -> 5 -> 6

注意：其实是非降序链表，所以包括 单节点的链表，想同数据的链表。（不过好像没什么太大关系哈哈哈）

思路：

1、拿任意一个链表(L1)与另一个链表(L2)对比，从头节点开始，如果**L1**大于等于

L2 的节点值就插入（指向的改变）到这个节点后面。

2、用什么算法可以实现？

1. 暴力

2. 递归 -- 解 1

3. 迭代 -- 解 2

解：

1. 递归

操作：

(1) 先判断两个链表的头结点谁大谁小。

if (L1Head ? L2Head);

(2) 根据两个链表从头节点开始的节点大小对比改变 节点指向，从而获得新的链表

如 L1 < L2 , 会出现 L1.next -> L2，再次递归 L2 的指向，L2.next -> 下一个（L1和L2）的对比。

▼
text
复制代码
L1 -> ( L1.next ? L2 ) -> L1.next（小） -> ( L1.next.next ? L2 )

                       -> L2（小） -> ( L1.next ? L2.next )

▼
java
复制代码
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;
        }
    }
}

2. 迭代

操作：

（1）设置一个哨兵节点-- prehead（更好返回链表），然后维护一个指针 prev，指针指向两个链表 L1 和 L2 当前节点 较小的节点，然后 指向完毕后 prev 会去到 prev指向的位置。

L1.val ? L2.val prev = prev.next;

（2）完成比较后，至多 有一个链表 会是 非空的，因为经过比较，所以这个链表包含的元素都比合并的目的链表中等元素都要大。这样我们可以直接将其简单的接在目的链表后即可完成最后的合并。

prev.next = L1 == null ? L2 : L1;

（3）最后可以通过 prehead.next 返回目的链表

▼
java
复制代码
class Solution {
    public ListNode mergeTwoLists( ListNode L1, ListNode L2 ) {
        // 后续需要注意 这个是新建节点 得用 new
        ListNode preNode = new ListNode(-1);
        ListNode prev = preNode;
        
        // 循环 对比节点值，并且完 成prev 指针的指向更改
        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;
        }
        
        // 合并 剩余的至多一个的非空链表
        prev.next = L1 == null ? L2 : L1;

        return preNode.next;
    }
}