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

【剑指offer系列题解】

【题目地址】

题目描述

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

数据范围

链表长度 [0,500]。

样例

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

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

方法一：二路归并 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) {}
 * };
 */classSolution{public:
    ListNode*merge(ListNode* l1, ListNode* l2){
        ListNode* head =newListNode(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;elseif(l2 !=NULL)    temp->next = l2;return head->next;}};

欢迎大家在评论区交流~