[数据结构与算法]LeetCode第21题—合并两个有序链表

本次写的题目是合并两个有序链表，为LeetCode里面的题目，让我们来康康是如何解出这道题目的吧，各位尚没有思路的小伙伴可以跟随着博主的解题思路一步步来，感受一下😎

🌱分析阶段

在本题中，如果要将两个有序链表合并到同一个链表内并有序，那么就需要比较两个链表中的每一个元素，然后像穿针线一样将两个链表串联起来，如下图👇：

?但是像这样子串联后list1或list2需要往后走以达到继续向链表中的元素比较的目的，所以此时我们需要再创建一个结点cur，来记录链表中两个结点比较中的小的那个结点，串联起来之后就需要头结点继续往后走继续比较，而cur就用于串联以及记录较小结点。

至此，将两个链表串联起来的大致思路完成了😎

?🌱代码阶段

在大致思路有了以后，我们就需要思考有没有一些特殊情况存在，我们需要考虑的特殊情况有两种情况：①两个链表其中有一个为null的时候；②在链表合并中有一个链表已经合并完而另一条链表还剩下很多元素

还有一个要考虑的是当我们的list往后走的时候要返回整个串联后的链表，是不是要拿一个结点先记录起来，所以综合考虑上面的情况，先写出如下代码👇：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;    //当list1为空链表，直接返回list2
        if(list2==null) return list1;    //当list2为空链表，直接返回list1
        ListNode newHead = new ListNode();    //创建一个结点，用于记录合并后链表的头结点
        ListNode cur = new ListNode();
        if(list1.val>list2.val){    //用于比较两个链表的头结点大小，小的头结点作为合并后链表的头结点来赋给newHead
            newHead = list2;
        }else{
            newHead = list1;
        }
    }
}

然后便是创建cur结点来记录小的结点与串联👇：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;    //当list1为空链表，直接返回list2
        if(list2==null) return list1;    //当list2为空链表，直接返回list1
        ListNode newHead = new ListNode();    //创建一个结点，用于记录合并后链表的头结点
        ListNode cur = new ListNode();
        if(list1.val>list2.val){    //用于比较两个链表的头结点大小，小的头结点作为合并后链表的头结点来赋给newHead
            newHead = list2;
        }else{
            newHead = list1;
        }
        while(list1!=null&&list2!=null){    //一直走到其中一个链表走完
            if(list1.val<=list2.val){
                cur.next = list1;    //cur带的位置就代表上一轮比较中较小的结点，在这一轮比较中将cur的next放入这轮较小的结点引用
                cur = list1;    //此时cur跑去这一轮较小结点的位置上
                list1 = list1.next;    //在这一轮中的较小结点list往后走
            }else{
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        return newHead;
    }
}

到此时代码还不算完整，我们还要考虑在链表合并中有一个链表已经合并完而另一条链表还剩下很多元素的这个情况，于是补充下面代码👇：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;    //当list1为空链表，直接返回list2
        if(list2==null) return list1;    //当list2为空链表，直接返回list1
        ListNode newHead = new ListNode();    //创建一个结点，用于记录合并后链表的头结点
        ListNode cur = new ListNode();
        if(list1.val>list2.val){    //用于比较两个链表的头结点大小，小的头结点作为合并后链表的头结点来赋给newHead
            newHead = list2;
        }else{
            newHead = list1;
        }
        while(list1!=null&&list2!=null){    //一直走到其中一个链表走完
            if(list1.val<=list2.val){
                cur.next = list1;    //cur带的位置就代表上一轮比较中较小的结点，在这一轮比较中将cur的next放入这轮较小的结点引用
                cur = list1;    //此时cur跑去这一轮较小结点的位置上
                list1 = list1.next;    //在这一轮中的较小结点list往后走
            }else{
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        if(list1==null){
            cur.next = list2;
        }
        if(list2==null){
            cur.next = list1;
        }
        return newHead;
    }
}

至此，所有代码就算完成了😎来运行逝逝

nice😎?