offer/src/18.h at master · feilongjiang/offer · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
 * @Author: FreedomLy
 * @Date: 2018-04-25 13:30:16
 * @Last Modified by: FreedomLy
 * @Last Modified time: 2018-04-25 13:51:02
 * 题目
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是
 * 按照递增排序的
 */

#pragma once

#include "ListNode.h"

class Solution18 {
public:
    // 遍历的方法
    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        if (!l1) return l2;
        if (!l2) return l1;

        ListNode* head = nullptr;

        if (l1->val < l2->val)
        {
            head = l1;
            l1 = l1->next;
        }
        else
        {
            head = l2;
            l2 = l2->next;
        }

        ListNode* p = head;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if (l1)
            p->next = l1;
        else
            p->next = l2;

        return head;
    }

    // 递归
    ListNode* merge_recursive(ListNode* l1, ListNode* l2)
    {
        if (!l1) return l2;
        if (!l2) return l1;

        ListNode* head = nullptr;
        if (l1->val < l2->val)
        {
            head = l1;
            head->next = merge_recursive(l1->next, l2);
        }
        else
        {
            head = l2;
            head->next = merge_recursive(l1, l2->next);
        }

        return head;
    }
};