【链表OJ题 4】合并两个有序链表

古城微笑少年丶 2023-09-27 19:27 97阅读 0赞

**目录**

题目来源：

代码实现：

思路分析：

实现过程：

--------------------

## 题目来源： ##

[21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)][21. _ - _LeetCode_ _leetcode-cn.com]

**题目描述：**

![1ab8c9ed1ada135eb83c34bcfa8b1b6a.png][]

## 代码实现： ##

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
        if (NULL == list1)
            return list2;
        if (NULL == list2)
            return list1;
    
        struct ListNode* head = NULL, * tail = NULL;
        while (list1 && list2)//有一个为空就跳出，后面直接把不为空的接上就可以
        {
            //尾插
            if (list1->val < list2->val)
            {
                if (NULL == tail)
                {
                    head = tail = list1;
                }
                else
                {
                    tail->next = list1;
                    tail = tail->next;
                }
    
                list1 = list1->next;
            }
            else
            {
                if (NULL == tail)
                {
                    head = tail = list2;
                }
                else
                {
                    tail->next = list2;
                    tail = tail->next;
                }
    
                list2 = list2->next;
            }
        }
    
        if (NULL == list1)//list1为空，直接把list2接在后面
            tail->next = list2;
        else
            tail->next = list1;
    
        return head;
    }

### 思路分析： ###

![cb99e53a11c1b00e08b9c828398dd385.png][]

为实现本题，我们要创建两个结构体指针，head 和 tail ，都初始化为NULL。我们的思路是对比两个链表的每个结点，将小的进行尾插。

#### 实现过程： ####

我们先处理特殊情况，如果 list1 或者 list2 某一个为空，那就返回另一个。

if (NULL == list1) return list2;
    if (NULL == list2) return list1;

1.比较 list1->val 与 list2->val，如果 list1->val 小，那就将 list1 作为新的头结点，让 head与tail 都赋值为 list1，插入后就让 list1 往后走一步。如果比较是相反的结果，那就将 list2 赋给 head与tail，list2 作为合成的头结点；

2.在比较新的 list1->val 与 list2->val 时，如果 list2->val 小，那就开始尾插，将 list2 赋给 tail->next，更新 tail，并更新 list2，让 list2 往后走一步。如果比较的结果相反，那就将 list1 赋给 tail->next，更新 tail 与 list1；

3. 循环步骤 1与2，当 list1/list2 任一走到空，就把不为空的那个链表直接接在 tail->next 上，并返回合成后的链表头 head。

![73d0690ce9fb40a4111701a2778e22b5.png][]

![8a1c71dbca070f42a661b7488863f048.png][]

\*\*\* 本篇结束 \*\*\*

[21. _ - _LeetCode_ _leetcode-cn.com]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[1ab8c9ed1ada135eb83c34bcfa8b1b6a.png]: https://img-blog.csdnimg.cn/img_convert/1ab8c9ed1ada135eb83c34bcfa8b1b6a.png
[cb99e53a11c1b00e08b9c828398dd385.png]: https://img-blog.csdnimg.cn/img_convert/cb99e53a11c1b00e08b9c828398dd385.png
[73d0690ce9fb40a4111701a2778e22b5.png]: https://img-blog.csdnimg.cn/img_convert/73d0690ce9fb40a4111701a2778e22b5.png
[8a1c71dbca070f42a661b7488863f048.png]: https://img-blog.csdnimg.cn/img_convert/8a1c71dbca070f42a661b7488863f048.png