剑指offer 24. 合并两个排序的链表

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围

链表长度 [0,500]。

样例

输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5
1
2
3

方法一：二路归并 O(n)

我们可以创建一个头指针，然后将两个链表用这个头指针串起来。我们拿样例举例，看看是如何实现的（下面的图中等于是另外创建了一个链表，实际上代码只用将两个链表的结点串起来即可，不用重新开辟 O(n) 的空间，但是为了更直观的给大家展示效果，我将 head 的链表单独拎了出来）：

第一步： 创建一个新的头结点。

第二步： 让 l1 和 l2 从头往后遍历链表，每次遍历的时候如果 l1 指向的结点值比 l2 指向的结点值小就将 l1 指向的结点加入 head 链表中；反之，就将 l2 指向的结点加入到 head 链表中。

（1）1 小于 2 ，将 1 加入链表中。

（2）2 小于 3 ，将 2 加入链表中。

（3）3 小于 4 ，将 3 加入链表中。

（4）4 小于 5 ，将 4 加入链表中。

（5）最后再将两个 5 分别加入到链表中。

第三步： 返回最终得到的链表，注意这里要返回的是 head->next ，因为 head 是我们创建出来的结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* temp = head;
        while (l1 != NULL && l2 != NULL)
        {
            if (l1->val < l2->val)
            {
                temp->next = l1;
                l1 = l1->next;
            }
            else
            {
                temp->next = l2;
                l2 = l2->next;
            }
            temp = temp->next;
        }
        if (l1 != NULL) temp->next = l1;
        else if (l2 != NULL)    temp->next = l2;
        return head->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

欢迎大家在评论区交流~