图解LeetCode——合并两个有序链表

如果你喜欢这篇文章的话，请给作者点赞+关注哟，你的支持是我不断前进的动力！

题目描述：

解法：

完整代码：

结果

题目链接：力扣

题目描述：

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

示例 1：

格式：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        //代码
    }
}

解法：

第一步：

我们需要一开始设置一个虚拟节点，它的值为 -1(它的值可以设置为任何的数)，我们在后序的操作中不需要关心它具体的值，设置任何值都可以，并且我们设置一个p指针指向它。

ListNode dummy = new ListNode(-1), p = dummy;

第二步：

为了方便我们后序代码的输入，我们分别给两个链表取个别名（可以不取）。

 ListNode p1 = list1;
 ListNode p2 = list2;

第三步：

使用while循环，当我们的两个链表都不为空的时候进行遍历，在遍历的过程中不断的比较他们之间的值，让p的next指向值小的那一个。

这个时候我们发现，链表一的值比链表二的值要小，我们将其放入到新链表中，完成后让 p1 = p1.next; p = p.next

 while(p1 != null && p2 != null){
            if(p1.val > p2.val){
                p.next = p2;
                p2 = p2.next;
            }else{
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }

这个时候我们发现链表一已经为空了，但是链表二还没有为空，这个时候我们只需要将链表二后面的结点拼接到新链表上就可以啦

if(p1 != null){
    p.next = p1;
 }
if(p2 != null){
    p.next = p2;
 }

这个时候我们只需要返回虚拟结点的下一个结点就是我们的新链表啦

完整代码：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while(p1 != null && p2 != null){
            if(p1.val > p2.val){
                p.next = p2;
                p2 = p2.next;
            }else{
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }

        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
        return dummy.next;
    }
}