【刷题篇】链表（上）

快来打我* 2024-04-25 20:02 70阅读 0赞

![e0adafd82c7ecf0141a6e549649881cb.gif][]

1.  ### 前言? ###

前段时间我们学习了单向链表和双向链表，本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说，让我们进入今天的题目吧！

> ?本期的题目有： 反转单链表、 链表的中间结点、 合并两个有序链表

1.  ### [反转单链表][Link 1]✨ ###

#### a.题目 ####

![85301d2d90b64caebf1582a918b38214.png][]

#### b.题解分析(迭代) ####

?**三指针法:**我们可以直接在原链表的基础上修改指针的指向，定义三个指针对链表每个结点的指针进行反转，循环直到链表结束。具体过程动图如下：

![5d26844c983eeaa128ca78bcdb1f904e.gif][]

?**头插法：**在我们对链表进行进行头插时，假设依次插入1，2，3三个结点，最后结点的就是3，2，1，刚好相反。我们可以利用这个特性对链表进行反转，创建一个头指针指向一个空链表，然后遍历原链表的结点，将结点以头插的形式头插到新的链表中，最终新链表即为我们所需的反转链表(由于在头插过程中会改变结点的指向，所以我们也需要保存原链表的下一结点)。具体过程动图如下：

![c9330c2aba2841c17b729dbc0681796f.gif][]

#### c.AC代码(迭代) ####

struct ListNode 
    {
        int val;
        struct ListNode *next;
    };
    
    //三指针法
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* n1 = NULL;
        struct ListNode* n2 = head;
    
        while (n2)
        {
            struct ListNode* n3 = n2->next; //保存下一结点位置
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }
        //n2为空时，n1即为反转后表头
        return n1;
    }
    
    //头插法
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* newhead = NULL; //新链表
        struct ListNode* first = head;
        while (first)
        {
            struct ListNode* next = first->next; //保存下一结点
            //进行头插
            first->next = newhead;
            newhead = first;
            first = next;
        }
        //全部结点头插完毕
        return newhead;
    
    }

#### d.题解分析(递归) ####

除了用上面迭代的方式，我们还可以用递归的方式来实现反转链表，这会让代码更加简洁。我们可以先使用递归函数找到链表尾记为ret，ret即为反转后链表的头结点。当找到头结点后，递归函数开始返回，每次将当前结点的下一结点的next指针指向当前结点。由于递归返回是逆向的，因此当递归函数全部出栈后，链表的反转也就完成了。具体过程动图如下：

![8f89f606f5aa22aa1e07c2b816eddb15.gif][]

#### e.AC代码(递归) ####

struct ListNode 
    {
        int val;
        struct ListNode *next;
    };
    //递归法
    struct ListNode* reverseList(struct ListNode* head) 
    {
        if (head == NULL || head->next == NULL) //当只有一个结点、没有结点、递归到最后一个结点时返回
            return head;
        struct ListNode* cur = reverseList(head->next); //找到链表尾结点
        head->next->next = head; //让下一结点指向当前结点
        head->next = NULL; //当前结点指向空
        return cur; //返回反转后头结点
    }

1.  ### [链表的中间结点][Link 2]? ###

#### a.题目 ####

![fb637ad6f14c4805b4232d7dcee82059.png][]

#### b.题解分析 ####

本题我们可以使用快慢指针的方法来解答。

> ✈ **快慢指针** ：含 快指针 和 慢指针 两个指针。快慢指针中的快慢指的是 移动的步长 ，即每次向前移动速度的 快慢 。例如可以让快指针每次沿链表向前移动2次，慢指针每次向前移动1次。

由于我们要求找到链表的中间结点，所以我们先定义一个快指针fast和一个慢指针slow指向第一个结点，然后让指针开始移动。规定快指针每次移动两步，慢指针每次移动一步，当快指针走到“链表尾”后，由于慢指针移动的步长为快指针一半，最后慢指针指向的即为链表的中间结点。

?本题有个需要注意的地方是：当链表的结点数为奇数时，链表只有一个中间结点，当快指针走到尾结点时慢指针即指向中间结点；但当链表的结点数为偶数时，快指针不可能走到尾结点，并且链表有两个中间结点，由于题目要求我们返回第二个结点，对应快指针指向空。**综上**，快指针fast移动停止的条件是fast == NULL || fast -> next == NULL。具体动图过程如下：

![b138a51c3797d96f76fca9e42c162587.gif][]

![950a642d4f98c03d10632002cb9f472f.gif][]

#### c.AC代码 ####

struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) //循环继续条件，对应于上述结束条件
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

1.  ### [合并两个有序链表][Link 3]? ###

#### a.题目 ####

![5d56cdfe49cb4ae98461d52b86680bfa.png][]

#### b.题解分析 ####

这道题和合并两个有序数组有异曲同工之妙，只不过我们要合并的是链表，而不是数组。我们可以从左到右遍历两个链表比较结点的大小，将小的结点尾插到新链表。注意不是创建一个新结点然后尾插，题目要求新链表是通过已有结点拼接而成的。当一个链表遍历完毕后将另外一个链表的剩余结点尾插到新链表后即可完成合并。

我们在前面学习链表尾插时，不难发现，如果链表没有带哨兵位的头结点，尾插时需要额外考虑链表为空的情况，而我们正是需要从空链表开始尾插，所以为了代码简洁，我们可以创建带哨兵位的头结点来指向链表的有效部分，这样可以不需要进行分类讨论。具体过程动图如下：

![3de3bef7a90a003c06f882e4763349b0.gif][]

#### c.AC代码 ####

struct ListNode 
    {
         int val;
         struct ListNode *next;
     };
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
    {
        struct ListNode* head = malloc(sizeof(struct ListNode)); //创建头结点
        head->next = NULL;
        struct ListNode* tail = head; //tail代表尾结点
        struct ListNode* p1 = list1;
        struct ListNode* p2 = list2;
        //遍历比较，尾插
        while (p1 != NULL && p2 != NULL)
        {
            if (p1->val > p2->val)
            {
                //把list2尾插到tail结点后
                tail->next = p2;
                tail = tail->next;
                p2 = p2->next;
            }
            else
            {
                //把list1尾插到tail结点后
                tail->next = p1;
                tail = tail->next;
                p1 = p1->next;
            }
    
        }
        //有一个链表遍历完毕
        if (p1)
        {
            //将p1及以后结点尾插
            tail->next = p1;
        }
        else if (p2)
        {
            //将p2及以后结点尾插
            tail->next = p2;
        }
        struct ListNode* cur = head->next; //头结点指向的部分即为我们所需的结果
        free(head); //释放创建的头结点
        return cur;
    }

--------------------

***以上，就是本期的全部内容啦***?

***制作不易，能否点个赞再走呢***?

[e0adafd82c7ecf0141a6e549649881cb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3f20677035dc4a53a00388fcb8fd4328.gif
[Link 1]: https://leetcode.cn/problems/reverse-linked-list/
[85301d2d90b64caebf1582a918b38214.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/7ae5c6a2d2dd49388e5ebb69bbbd74d7.png
[5d26844c983eeaa128ca78bcdb1f904e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/801507668ee0499b82593222f50c1a17.gif
[c9330c2aba2841c17b729dbc0681796f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/618571d30cc74993a9a09fdb5ffef14c.gif
[8f89f606f5aa22aa1e07c2b816eddb15.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/86c2a8d5261c4657b00f9002a02fa603.gif
[Link 2]: https://leetcode.cn/problems/middle-of-the-linked-list/
[fb637ad6f14c4805b4232d7dcee82059.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/7218807f628b490b8e4f20a365eaa28d.png
[b138a51c3797d96f76fca9e42c162587.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f98baebbed6b4283a56d6d29b213cdc8.gif
[950a642d4f98c03d10632002cb9f472f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9ec2229de03f4bd9937096461d4ddc80.gif
[Link 3]: https://leetcode.cn/problems/merge-two-sorted-lists/
[5d56cdfe49cb4ae98461d52b86680bfa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c79ca7ae0ac44a9cad06516b8a62fa5f.png
[3de3bef7a90a003c06f882e4763349b0.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f06dc2e301a5423fbd76b8f5cf13fd2a.gif