链表OJ题(五)

1. 合并两个有序链表

链接：21. 合并两个有序链表

描述：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例2：
输入：l1 = [], l2 = []
输出：[]
示例3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

1.1 思路–带哨兵位的头结点

之前做过一道题目，叫做合并两个有序数组。其中有一种方法是创建一个新数组，然后遍历两个数组，将两个数组的较小的元素放置到新数组中。一个数组遍历完，将没有放置的元素放置到新数组中，然后拷贝回原数组。

那么这道题能否借鉴它的思路？
合并两个有序链表，链表和数组不同，数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系，所以不需要创建新链表，只需要修改即可。
有序数组的做法是将较小元素逐个尾插到新数组中，那么我们也可以将较小元素尾插到链表中。

那么链表为空如何处理？
这时就又要用到哨兵位(头结点)了，我们给一个哨兵位 head，它也不存储数据，那么不就可以了？但是注意有效数据从 head->next 开始。
在这里插入图片描述

但是尾插存在两个问题，当尾插的时候，我们需要找链表的尾，而且当链表为空时，需要特殊处理。为了避免每次找链表的尾，那么我们就给定一个 tail，这样只要将 tail 迭代就可以。
在这里插入图片描述

注意：哨兵位需要释放，否则会造成内存泄漏。
在这里插入图片描述

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL, *tail = NULL;
    if (list1 == NULL)
    {
        return list2;
    } 
    if (list2 == NULL)
    {
        return list1;
    }
    // 哨兵位
    // 这里 tail 也需要动态开辟一下
    // 因为不在迭代时进行第一次插入的处理
    // tail 一开始为空指针，会报错
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1; // 当前结点链表的尾链接到 list1
            tail = list1; // 链表的尾变成 list1
            list1 = list1->next; // list1 并没有改变，list1 迭代到list1的下一个节点
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    // 未放置完的元素
    // 这里和数组的完全不一样
    // 链表是串联的，所以只需要把当前节点给到tail->next
    // 就可以全部串联
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
    // 释放哨兵位
    struct ListNode* ans = head->next;
    free(head); 
    return ans;
}

在这里插入图片描述

1.2 思路–不强行加头结点

这道题目不使用哨兵位也能写，但是使用这种方法时，需要处理一下链表第一次合并时尾插的情况，大体思路和带哨兵位差不多，但需要注意一下细节

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    struct ListNode *head, *tail;
    head = tail = NULL;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            // 第一次合并
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            // 第一次合并
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    return head;
}