力扣hot100——第4天：19删除链表的倒数第N个节点、20有效的括号、21合并两个有序链表

1.19删除链表的倒数第N个节点【代码随想录已刷】

参考：力扣题目链接；自己的博客解答

2.20有效的括号【代码随想录已刷】

参考：力扣题目链接；自己的博客解答

3.21合并两个有序链表

参考：力扣题目链接；题解

3.1.题目

3.2.题解

这道题目其实很简单，因为两个链表都是已经排序好的，结果只需要同时遍历两个链表的节点，然后判断那个数值更小，然后就选择哪个节点即可。然后再继续往后遍历后面的节点。

需要注意的是，这里要使用一个虚拟头节点来引导生成的链表，这样更方便编程。

注意：这道题目总记得非常熟悉，实际上有一道相加两个链表的节点的题目，跟这道题目非常像。

最后给出代码如下，非常简单：

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
{
    ListNode* dummy = new ListNode(0);  // dummy虚拟头节点
    ListNode* cur = dummy;

    // 遍历list1和list2，都不能是空
    while(list1 && list2)
    {
        // 选择小的那个数，作为下一个节点
        if(list1->val < list2->val)
        {
            cur->next = list1;
            list1 = list1->next;
        }
        else
        {
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }   

    // 到了这个地方之后，list1和list2中可能有非空的，那么就把剩下的再拼接到cur中
    // 如果list1和list2都是空，那么结果就是走else，cur->next也是空，也是符合要求的
    if(list1)
        cur->next = list1;
    else
        cur->next = list2;
    
    // 最后把拼接后的头节点取出来，并把dummy节点删掉
    ListNode* res = dummy->next;
    delete dummy;
    
    return res;
}
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