题目描述：

在这里插入图片描述

题解一：链接+排序

  1. 直接拼接两个链表
  2. 给链表排序
  3. 输出链表头结点
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
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
    int len(ListNode* head)
    {
        int count = 0;
        while(head != nullptr)
        {
            ++count;
            head = head->next;
        }
        return count;
    }
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;
        ListNode* ptr1 = list1;
        ListNode* ptr2 = list2;
        while(nullptr != ptr1->next)
        {
           ptr1 = ptr1->next;
        }
        ptr1->next = ptr2;
        //给ptr1排序并返回list1;
        const int count = len(list1);
        int* arr = new int[count];
         //赋值
         ptr2 = list1;
        for(int i = 0; ptr2 != nullptr; ++i, ptr2 = ptr2->next)
        {
            arr[i] = ptr2->val;
        }
        sort(arr,arr + count);
        ptr2 = list1;
        for(int i = 0; ptr2 != nullptr; ++i,ptr2 = ptr2->next)
        {
            ptr2->val = arr[i];
        }
        delete[] arr;
        return list1;
    }
};

在这里插入图片描述

题解二：新头结点链接

思路：

  1. 使用一个新的头结点head
  2. 循环将两个链表的结点依次比较
  3. 较小者申请新结点链接到head后
  4. 循环退出后，链接剩余链表的结点
  5. 返回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
    33
    34
    35
    36
    37
    38
    39
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
            if(list1 == nullptr) return list2;
            if(list2 == nullptr) return list1;
            ListNode* ptr1 = list1;
            ListNode* ptr2 = list2;
            //头结点
            ListNode* head = new ListNode();
            ListNode* p =  head;
            while(ptr1 != nullptr && ptr2 != nullptr)
            {
                if(ptr1->val < ptr2->val)
                {
                    p->next = new ListNode(ptr1->val, nullptr);
                    ptr1 = ptr1->next;
                }
                else
                {
                    p->next = new ListNode(ptr2->val, nullptr);
                    ptr2 = ptr2->next;
                }
                p = p->next;
            }   
            while(ptr1 != nullptr)
            {
                p->next = new ListNode(ptr1->val, nullptr);
                ptr1 = ptr1->next;
                p = p->next;
            }
            while(ptr2 != nullptr)
            {
                p->next = new ListNode(ptr2->val, nullptr);
                ptr2 = ptr2->next;
                p = p->next;
            }
            return head->next;
        }
    };
    在这里插入图片描述

    题解三：递归

    在这里插入图片描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr || list2 == nullptr)
        {
            return list1 == nullptr ? list2 : list1;
        }
        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }  
        else
        {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }  
    }
};