0. 前言

上篇博客中，我们学习了实现了单链表。但是仅仅实现并不算掌握，所以我们需要做些题目来练习巩固。而从今天开始的几期，anduin 都会为大家带来链表OJ题，并配上详细题解和图解，来帮助大家更好的理解。今天为大家带来的是 移除链表元素、反转链表、合并两个有序链表 三道题目。话不多说，我们这就开始。

1. 移除链表元素

链接：203. 移除链表元素

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例2：

输入：head = [], val = 1
输出：[]

示例3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

思路1(精讲)：

考察的为单链表元素的删除。

遍历链表，用变量 prev 记录遍历链表时每个节点的上一个节点。变量 cur 为本次节点。

如果第一个节点的值域和 val 相等，为 头删 情况，此时记录本节点的下一个节点，将头变为本节点的下一个节点，释放本节点，迭代 cur 。

如果节点的值和 val 相等且 不为头删 情况，那么将 prev 的 next 和 cur 的 next 链接(prev->next = cur->next)，然后释放 cur 节点，将cur变为 prev 的next，也就是之前当前节点的下一个节点。

如果这两个条件不满足，则将 prev 和 cur 迭代向后走。

最后返回 head 头。

思路2(精讲)：

尾插法。

总体思路是这样的，遍历链表，将节点的值不为 val 的节点尾插到新链表中，如果等于 val 就迭代往后走，直到链表为空。

但是尾插需要特殊考虑空链表尾插的情况，实际上写起来还是比较烦的，所以这时我们就可以用到上篇博客中提到的哨兵位(哑节点)。

先给定一个 cur 作为遍历原链表的指针。

我们先动态开辟一个哨兵位 dummy 。每次尾插时，都需要找到尾部，那么再给定一个 tail 让其等于 dummy 。这样改变 tail 的链接的时候，也就相当于改变了新链表。

接下来就是常规操作，使用 cur 遍历链表，如果 cur 对应节点的值不等于 val ，那么就对新链表进行尾插，这时由于链表一定不为空，于是直接将 tail->next 链接为 cur 即可，再使 tail 、cur 向后迭代。

如果 cur 对应节点的值等于 val ，那么就说明这为需要删除的节点，那么先拷贝 cur 的下一个节点，再释放该节点，再cur 迭代往后走。

注意：如果 tail 最后链接的节点不是原链表的最后一个节点，那么 tail->next 还链接着原链表，而一旦原链表的节点已经被释放，这就导致了野指针。所以需要断开链接，链到空(tail->next = NULL)。

2. 反转链表

链接：206. 反转链表

描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例3：

输入：head = []
输出：[]

思路1(精讲)：

迭代法。

我们想象一下，原先链表的第一个节点链接着第二个节点，那我们是否可以将第二个节点链接到第一个节点？再将其他元素逐次链接，第一个节点链接到空指针。就像这样：NULL ← ① ← ②

这当然可以，因为这就是当前思路的主要方法。

我们需要三个变量，n1 记录上一个节点， n2 记录当前节点，n3记录下一个节点。

然后通过 n2 遍历链表，将链表节点逐个反转，然后利用 n2 使 n1 迭代到当前节点的位置，利用 n3 使 n2 迭代到下一个节点，这两个步骤的次序一定不能乱。上面两个步骤完成后，如果 n3 不为 NULL ，那么让 n3 也迭代到它的下一个节点处。

最后返回 n1 就是反转后的链表。

注意点：空链表需要特判。

思路2(精讲)：

头插法。

给定 cur 用来遍历链表，newhead为链表的新头。

遍历链表，记录 cur 的下一个节点(cur->next)，然后将这个节点头插到 newhead前，将 newhead 赋值为 cur，到最后newhead 就是之前链表的最后一个节点，返回即可。

3. 合并两个有序链表

链接：21. 合并两个有序链表

描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2：

输入：l1 = [], l2 = []
输出：[]

示例3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路(精讲)：

我们之前做过一道题目，叫做合并两个有序数组。其中有一种方法是创建一个新数组，然后遍历两个数组，将两个数组的较小的元素放置到新数组中。一个数组遍历完，将没有放置的元素放置到新数组中，然后拷贝回原数组。

那么我们这道题能否借鉴它的思路？

我们这道题为合并两个有序链表，链表和数组不同，数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系，所以我们不需要创建新链表，只需要修改即可。

有序数组的做法是将较小元素逐个尾插到新数组中，那么我们也可以将较小元素尾插到链表中呀。

但是尾插就有两个问题，当尾插的时候，我们需要找链表的尾，而且当链表为空时，需要特殊处理。

为了避免每次找链表的尾，那么我们就给定一个 tail，这样只要将 tail 迭代就可以。

那么链表为空如何处理？难道在循环中特判，然后每次迭代的时候都判断一次，那也太麻烦了，而且也会代码冗余。

那么这时就又要用到哨兵位(头结点)了，我们给一个哨兵位 head，它也不存储数据，那么不就可以了？但是注意有效数据从 head->next 开始。

注意：哨兵位需要释放，否则会造成内存泄漏。

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL, *tail = NULL;
    if (list1 == NULL)
    {
        return list2;
    } 
    if (list2 == NULL)
    {
        return list1;
    }
    // 哨兵位
    // 这里 tail 也需要动态开辟一下
    // 因为不在迭代时进行第一次插入的处理
    // tail 一开始为空指针，会报错
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1; // 当前结点链表的尾链接到 list1
            tail = list1; // 链表的尾变成 list1
            list1 = list1->next; // list1 并没有改变，list1 迭代到list1的下一个节点
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    // 未放置完的元素
    // 这里和数组的完全不一样
    // 链表是串联的，所以只需要把当前节点给到tail->next
    // 就可以全部串联
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
    // 释放哨兵位
    struct ListNode* ans = head->next;
    free(head); 
    return ans;
}

这道题目不使用哨兵位也能写，但是使用这种方法时，需要处理一下链表第一次合并时尾插的情况，大体思路和带哨兵位差不多，只是需要注意一下细节，这里我就不多赘述了，大家可以自己试试，下面贴下截图和代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    struct ListNode *head, *tail;
    head = tail = NULL;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            // 第一次合并
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            // 第一次合并
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    return head;
}

4. 结语

到这里，本篇博客就到此结束了，建议大家在看完博客后，再下去写一写。从 理解 → 独立想出思路 → 画图 → 完整实现代码。会写一道题目不是在看完题解后，因为记住了代码，默写下来；而是能自己想出思路，能画出图，并自我实现，这样才算掌握。多写多练多画图，才能学好数据结构。

下篇博客我会继续更新链表的OJ题，我们敬请期待~

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！