合并两个有序链表

合并两个有序链表
题目给定：两个链表头类型为ListNode

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

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

我的解题思路：保持一个链表不动，把另一个链表中的元素依次插入中。其中的val值小于的val值。最后输出链表头

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //判断链表是否为空
        if (l1 == null && l2 != null) {
            return l2;
        } else if (l1 != null && l2 == null) {
            return l1;
        } else if (l1 == null && l2 == null) {
            return null;
        }
        //保证l1始终为较小的值，保证l2的第一个元素必然出现在l1的第一个元素后
        if (l1.val > l2.val) {
            ListNode tListNode = l1;
            l1 = l2;
            l2 = tListNode;
        }
        //暂存l1节点用于返回值
        ListNode starListNode = l1;
        
        //开始排序
        while (l1 != null && l2 != null) {
            if (l1.next == null && l2 != null) {
                //对应情况 [1] [2 .... ] 
                l1.next = l2;
                break;
            }
            while (l1.next.val < l2.val) {
                //对应情况 [1 2 4] [5 ....] 即l2的表头大于l1的表尾
                l1 = l1.next;
                if (l1.next == null && l2 != null) {
                //其实也可以这么写
                //直接拼接然后返回表头节点，使用break则由后续代码进行拼接
                //l1.next=l2
                //return starListNode
                    break;
                }
            }
            //下面为把l2节点插入到l1中
            ListNode temp_l2 = l2.next;
            l2.next = l1.next;
            l1.next = l2;
            l2 = temp_l2;
            l1 = l1.next;
        }
        return starListNode;
    }

这种写法的最大缺点是需要判断的临界值过多。

参考答案的解法则类似于再找一个链表，比较和的大小，把较小的一个放入中，若较小，则，反之亦然

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        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;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

另：递归解法理解
可以看到merge这个函数返回的是最后合并后的链表的头节点。当value小于时，的下一个节点是以为头的链表和为头的链表合并后形成的新链表的头节点。

或者

而这一部分可以通过比较的val和的val值，如果的话那么
或者

那么
以此类推直到没有下一个节点为止
可以看到整个过程可以不断使用merge这个函数，这大概就是递归的由来

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

    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。