合并两个有序链表

题目要求

链接：21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

图片说明

方法1：使用头指针

思路：

假设两个链表分别为l1和l2,l1和l2都是有序的
因为要排成升序，把l1和l2指向的结点的较小的尾插到新链表
由于是尾插到新链表：为了方便，可以定义两个指针，一个新链表的头，一个指向新链表的尾
这里使用的是头指针的写法：
- 首先：我们应该提前把l1和l2中的较小结点，尾插下来当头结点，更新尾指针
- 然后l1和l2继续向后比较，找到把小的尾插下去，然后更新尾指针
因为总有一个链表先遍历完(走到空)，把另一个没有遍历完的链表直接链接到尾指针后面即可(因为：l1和l2都是有序的)
然后返回新链表的头指针即可

注意： 如果其中一个链表一开始就是空，就返回另一个链表

图解

图片说明

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    //l1为空链表就返回l2
    if(l1 == NULL)
    {
        return l2;
    }
    //l2为空链表就返回l1
    if(l2 == NULL)
    {
        return l1;
    }

    //使用头指针  
    //定义头尾指针
    struct ListNode* head = NULL,*tail = NULL;
    //先从l1和l2选一个小的下来作为头，排升序
    if(l1->val val)
    {
        //头尾指针都要更新
        head = l1;
        tail = l1;
        //l1更小，l1继续往后走
        l1 = l1->next;
    }
    else
    {
        //头尾指针都要更新
        head = l2;
        tail = l2;
         //l1小，l2继续往后走
        l2 = l2->next;
    }
    //遍历比较 -如果有一个链表走完(空指针)就跳出循环
    while(l1 && l2)
    {
        if(l1->val > l2->val )
        {
            tail ->next = l2;//尾指针链接小的结点
            tail = l2;//更新尾结点
            l2 = l2->next;//小的结点的链表向后走
        }
        else{
            tail ->next = l1;//尾指针链接小的结点
            tail = l1;//更新尾结点
            l1 = l1->next;//小的结点的链表向后走
        }
    }
    //有一个结束了-未知是哪个先结束->两个都判断
    //下面的两个if判断，只进入一个
    if(l1)
    {
        tail->next = l1;//尾指针链接没有比较完的链表
    }
    else{
        tail->next = l2;//尾指针链接没有比较完的链表
    }
    return head;//返回新链表的头指针
}

方法2：使用哨兵位

思路：和上面方法1基本一致

假设两个链表分别为l1和l2,l1和l2都是有序的
使用了哨兵位，所以不需要先选一个下来当头结点
由于是尾插到新链表：为了方便，可以定义两个指针，一个新链表的头，一个指向新链表的尾
这里使用的是哨兵位的写法：
- 注意：哨兵位的next才是第一个结点，哨兵位不存储有效数据
- l1和l2从头开始向后比较，找到把小的尾插下去，然后更新尾指针
因为总有一个链表先遍历完(走到空)，把另一个没有遍历完的链表直接链接到尾指针后面即可(因为：l1和l2都是有序的)
然后返回新链表的头指针即可，返回的是head->next才是第一个结点

注意：最后哨兵位结点要释放掉

图片说明

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
    {
        return l2;
    }
    if(l2 == NULL)
    {
        return l1;
    }

    //使用哨兵位
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = head;

    //遍历比较 -如果有一个走完就跳出循环
    while(l1 && l2)
    {
        if(l1->val > l2->val )
        {
            tail->next =l2 ;
            tail = tail->next;
            l2 = l2->next;
        }
        else{
            tail->next = l1;
            tail = tail->next;
            l1 = l1->next;
        }
    }
    //有一个结束了
    if(l1)
    {
        tail->next = l1;
    }
    else{
        tail->next = l2;
    }
    //保存第一个结点，防止释放掉哨兵位之后找不到
    struct ListNode* tmp = head->next;
    //哨兵位结点要释放掉，然后置空
    free(head);
    head = NULL;
    return tmp;
}

#算法题#