《剑指offer-P23》【剑指Offer 25.合并两个排序的链表】

个人主页：企鹅不叫的博客

​ 专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

• 一、题目
• • 1.题目描述
  • 2.原题链接
• 二、解题报告
• • 1.思路分析
  • 2.代码详解

剑指Offer 25.合并两个排序的链表

思路：

​ 用一个哨兵将两个链表同时遍历链接起来，遍历完之后将剩余未链接的连接到新链表后面

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //带哨兵位
    struct ListNode* head, *tail;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));        //1
    head->next = NULL;

    while(list1 != NULL && list2 != NULL){                                  //2
        if(list1-> val < list2-> val){
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }else{
            tail -> next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if(list1 != NULL){                                                      //3
        tail->next = list1;
    }
    if(list2 != NULL){
        tail->next = list2;
    }
    struct ListNode* list = head->next;                                     //4
    free(head);
    return list;                                                            //5
}

1.创建哨兵节点
2.两个链表同时遍历
3.将两个链表剩余部分继续链接到新链表上
4.为方便释放内存，提前记录头
5.返回哨兵位下一位