LeetCode每日一练 —— 21. 合并两个有序链表

前言

Wassup guys！我是Edison

今天是 LeetCode 上的 leetcode 21. 合并两个有序链表

Let’s get it！

---

---

1. 题目分析

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

示例 1：

示例 2：

示例 3：

2. 题目图解

这道题其实就是 归并 思路，每次取小的节点 尾插 到新链表

思路一

定义指针 list 1 指向第一个链表的 头节点，定义指针 list 2 指向第二个链表的 头节点；

再定义一个新链表，此时头节点 head 和 尾节点 tail 都为 NULL，如图所示

我们分析一下 尾插 的过程：

第 1 次，当 list 1 等于 list 2 时，就把 list 1 插入到新链表中，给 head 和 tail；

第 2 次，当 list 2 小于 list 1 时，就把 list 2 插入到新链表中，更新 tail；

第 3 次，当 list 1 小于 list 2 时，就把 list 1 插入到新链表中，更新 tail；

这里直接看动图演示

注意：

当其中任意一个链表指向 NULL 时，把剩余的链表的元素直接 拷贝 到新链表中。
 
比如，list 1 先指向 NULL，那么直接把 list 2 剩余的元素拿到 新链表 中，也不用再更新 tail 了，直接返回新链表的 头节点。

为什么不更新 tail 呢？

我们要返回的是 头节点 ，又不用返回新的 尾节点，这里定义的 tail 只是方便进行 尾插。

接口代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    if (list1 == NULL) {
    
        return list2;
    }
    if (list2 == NULL) {
    
        return list1;
    }
    struct ListNode* head = NULL, *tail = NULL;
    while (list1 && list2) {
    
    	// list1 小于 list2
        if ((list1->val) < (list2->val)) {
    
            if (tail == NULL) {
    
                head = tail = list1;
            }
            else {
    
                tail->next = list1;
                tail = list1;
                // tail = tail->next
            }
            list1 = list1->next;
        }
        // list1 大于等于 list2
        else {
    
            if (tail == NULL) {
    
                head = tail = list2;
            }
            else {
    
                tail->next = list2;
                tail = list2;
                // tail = tail->next
            }
            list2 = list2->next;
        }
    }
    if (list1) {
    
        tail->next = list1;
    }
    if (list2) {
    
        tail->next = list2;
    }
    return head;
}

提交结果

思路一

我们可以新建一个 带头节点 的新链表，也就是 哨兵位 的头节点，这个节点不存储有效数据。

那么这个 带头 和 不带头 的区别在哪里呢？

在 思路一 中，我们定义的新链表是不带头的，head 和 tail 都指向 NULL，所以在插入时，要进行判断，tail 是否为 NULL 的情况。
 
那么如果我设置一个 哨兵位 的头节点，那么根本不需要判断，哪怕此时一个值都没有，head 和 tail 都不可能为 空，所以在进行 尾插 时，直接把元素插入到 哨兵位 后面即可。

原理还是和 思路一 是一样的，所以直接看动图

注意：

返回的时候，不能返回 head，而是返回 head 指向的 next，也就是 哨兵位 的下一个节点；
 
因为题目给的两个链表是不带哨兵位的，所以我们合并以后，返回的也是不带哨兵位的

接口代码

// 带头节点的单链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    
    struct ListNode* head = NULL, *tail = NULL;

    // 设置一个哨兵位
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;

    while (list1  && list2) {
    
        if ((list1->val) < (list2->val)) {
    
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else {
    
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if (list1) {
    
        tail->next = list1;
    }
    if (list2) {
    
        tail->next = list2;
    }

    // 释放
    struct ListNode* list = head->next;
    free(head);
    return list;
}

提交结果