题意分析

  • 这个题目会给我们两个有序的链表，然后我们需要将两个有序的链表合并，然后得到一个新的有序的链表，返回这个链表的头指针即可。

思路分析

前置知识

  • 我们首先观察这两个链表的特点，我们发现这两个链表都是有序的，然后最后合并成一个有序的链表。这个特点其实和我们的归并排序的思想是一样的。归并排序就是先将一个要排序的区间切分成log份，然后可以通过先将小区间排序，然后对于排好序的区间，我们将这两个区间进行合并成一个新的有序的区间，最终合并成一个全部有序的区间。

图片说明

大家可以结合这个图进行理解，归并排序的时间复杂度为nlogn。这是一种很高效的排序方式。

解法一 C++版

  • 这个题目其实就是一个归并的思想，对于两个有序的区间，我们只需要对他进行一次归并就可以合并这个区间了。具体的方法就是

    • 我们先找到两个链表的头指针中更小的作为最终链表的头指针。
    • 对两个链表进行遍历，找到更小的那个指针的值作为下一个结点。直到有一个链表到了链表尾部。
    • 对没有遍历完的链表继续进行遍历，返回最开始的头节点。

  • 代码如下

    • 需要遍历两个链表的每一个结点，所以时间复杂度为O(n+m)，n和m分别为两个链表的长度
    • 并未开辟新的内存空间，所以空间复杂度为O(1) 
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        // 对链表为空的情况进行判断
        if(l1==NULL&&l2==NULL) return NULL;
        else if(l1==NULL&&l2!=NULL) return  l2;
        else if(l1!=NULL&&l2==NULL) return l1;
        ListNode *root = new ListNode(-1);
        // 在两个链表都不是空的情况下，判断哪个链表的头指针可以作为最终的头指针
        if((l1->val)<(l2->val)){
            root=l1;
            l1=l1->next;
        }
        else{
            root=l2;
            l2=l2->next;
        }
        // 记录下新形成的链表的头结点指针
        ListNode *head=root;
        // 用一个while对两个链表不断遍历，每次遍历找到更小的那个指针作为下一个指针
        while(l1!=NULL&&l2!=NULL){
            // 将更小的结点指针作为下一个指针
            if((l1->val)>(l2->val)){
                root->next=l2;
                l2=l2->next;
            }else{
                root->next=l1;
                l1=l1->next;
            }
            root=root->next;
        }
        // 退出while的时候，一定是有一个链表为空，再次对两个链表进行遍历
        while(l1){
            root->next=l1;
            l1=l1->next;
            root=root->next;
        }
        while(l2){
            root->next=l2;
            l2=l2->next;
            root=root->next;
        }
        return head;
    }
};

解法二 Go语言版

  • Go语言具体的思路其实也是一样的。
    • 我们先找到两个链表的头指针中更小的作为最终链表的头指针。
    • 对两个链表进行遍历，找到更小的那个指针的值作为下一个结点。直到有一个链表到了链表尾部。
    • 对没有遍历完的链表继续进行遍历，返回最开始的头节点。
  • 代码如下
    • 需要遍历两个链表的每一个结点，所以时间复杂度为O(n+m)，n和m分别为两个链表的长度
    • 并未开辟新的内存空间，所以空间复杂度为O(1) 
package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param l1 ListNode类 
  * @param l2 ListNode类 
  * @return ListNode类
*/
func mergeTwoLists( l1 *ListNode ,  l2 *ListNode ) *ListNode {
    // write code here
    // 特殊情况进行判断
    if l1==nil&&l2==nil {
        return nil
    } else if l1!=nil &&l2==nil{
        return l1
    }else if l1==nil&&l2!=nil{
        return l2
    }
    // 到了这步说明这两个链表都不是空的了
    var root *ListNode
    // 寻找出那个链表的头指针适合用来作为最终的头指针
    if l1.Val>l2.Val {
        root=l2;
        l2=l2.Next
    }else{
        root=l1;
        l1=l1.Next
    }
    head := root
    // 对两个链表进行遍历，直到一个链表到了最后
    for l1!=nil&&l2!=nil {
        if l1.Val>l2.Val {
            root.Next=l2
            l2=l2.Next
            root=root.Next
        }else{
            root.Next=l1
            l1=l1.Next
            root=root.Next
        }
    }
    // 对没有遍历完的链表进行继续遍历
    for l1!=nil {
        root.Next=l1
        l1=l1.Next
        root=root.Next
    }
    for l2!=nil {
        root.Next=l2
        l2=l2.Next
        root=root.Next
    }
    // 返回头指针
    return head
}