Leetcode 21. 合并两个有序链表

1、问题分析

题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
  本质上就是一个链表操作问题。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

2、问题解决

  笔者以C++方式解决。

#include "iostream"

using namespace std;

#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "cstring"
#include "stack"

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
    // 定义新链表的头结点
    ListNode *headNode = NULL;
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // 如果 有一个链表为空，则不需要合并，直接返回另外一个链表即可
        // 即使另外一个链表为空，那正好结果就是空
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }

        // 合并两个链表
        dealChen(l1, l2);
        return headNode;
    }

    /**
     * 合并两个链表，
     * 定义 本节点为正在处理的节点
     * @param l1
     * @param l2
     */
    void dealChen(ListNode *l1, ListNode *l2) {
        // 首先设置头结点。根据 l1 链表和l2 链表头结点的值，确定哪个是头结点
        // 即哪个小，哪个就是头结点
        if (l1->val <= l2->val) {
            headNode = l1;
        } else {
            headNode = l2;
        }

        // 定义前置节点，初始时前置节点为空
        ListNode *preNode = NULL;
        // 如果两个链表都有值
        while (l1 != NULL && l2 != NULL) {
            // 如果  l1 链表的值较小，则选取本节点为 l1 节点
            // 否则选取本节点为 l2 节点
            if (l1->val <= l2->val) {
                // 前置节点不为空
                if (preNode != NULL) {
                    // 设置前置节点的下一个几点是本节点
                    preNode->next = l1;
                }
                // 进入下一个循环的时候，前置节点就是本节点
                preNode = l1;
                // 本节点处理完成，更新本节点为下一个节点，继续按照上述步骤处理
                l1 = l1->next;
            } else {
                // 前置节点不为空
                if (preNode != NULL) {
                    // 设置前置节点的下一个几点是本节点
                    preNode->next = l2;
                }
                // 进入下一个循环的时候，前置节点就是本节点
                preNode = l2;
                // 本节点处理完成，更新本节点为下一个节点，继续按照上述步骤处理
                l2 = l2->next;
            }
        }
        // 如果剩余的链表没有处理完成，则直接链接到 前置节点后面
        // 下面两个 if 语句最多只有一个可以执行
        if (l1 != NULL) {
            preNode->next = l1;
        }
        if (l2 != NULL) {
            preNode->next = l2;
        }
    }
};

int main() {
    ListNode *pNode11 = new ListNode(1);
    ListNode *pNode12 = new ListNode(2);
    ListNode *pNode13 = new ListNode(4);

    pNode11->next = pNode12;
    pNode12->next = pNode13;
    pNode13->next = NULL;

    ListNode *pNode21 = new ListNode(1);
    ListNode *pNode22 = new ListNode(3);
    ListNode *pNode23 = new ListNode(4);

    pNode21->next = pNode22;
    pNode22->next = pNode23;
    pNode23->next = NULL;

    Solution *pSolution = new Solution;
    ListNode *pNode = pSolution->mergeTwoLists(pNode11, pNode21);
    while (pNode != NULL) {
        cout << pNode->val << " ";
        pNode = pNode->next;
    }
    cout << endl;
    system("pause");
    return 0;
}
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

运行结果

有点菜，有时间再优化一下。

3、总结

  难得有时间刷一波LeetCode, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！
哪怕只有一个人从我的博客受益，我也知足了。
点个赞再走呗！欢迎留言哦！