合并有序链&&反转链表（递归版）

用户11029129

发布于 2024-06-04 13:53:28

1240

发布于 2024-06-04 13:53:28

文章被收录于专栏：编程学习

每日一题系列（day 19）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

一、合并有序链表

题目：

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

示例1：

示例2：

提示：

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

题解：

虽然合并有序链表是一道极为简单的题，但是这道题也是可以慢慢锻炼我们的递归思想，由浅入深。 所谓递归，当有重复子问题出现的时候可以采用的一种方法。题目给出了两个重要条件，1：不能手动创建新的节点。2：两个链表都是升序的链表。合并这两个链表，并且保证合并后的链表依旧是有序的，所以我们只能从链表的头按照顺序开始合并。
假设有两个三节点的链表，分别为l1，l2链表。首先，比较l1，l2的头结点，l1 -> val > l2 -> val，那么第一个节点我们就确定了，我们只需要将剩下的五个节点再比较出下一个节点，以此例推，直到指向空，最后返回即可。 注意：如果合并链表时其中一个链表已经指向了空，而另外一个链表 还没遍历完，这时只需要将指向空的那个链表直接指向未遍历完的链表即可（别忘了链表递增这个条件）。

代码演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //merge Two Lists
        if(list1 == nullptr) return list2;//第一个链表遍历完，则剩下的指向下一个链表
        if(list2 == nullptr) return list1;//同理，第二个链表遍历完，指向剩下的第一个链表
        
        if(list1 -> val < list2 -> val)
        {
            list1 -> next = mergeTwoLists(list1 -> next, list2);//如果l1<l2进行l1的递归
            return list1;
        }
        else
        {
            list2 -> next = mergeTwoLists(list1, list2 -> next);//否则进行l2的递归
            return list2;
        }
    }
};

二、反转链表

题目：

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

示例1：

示例2：

示例3：

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题解：

反转链表想必大家也都做过，其实这题也是可以使用递归来做的，准确说一点可以使用dfs来做。我们把链表竖起来，其实就是一棵树，而我们想要链表翻转，我们就需要从树的叶子结点开始向上操作，而每一步操作都可以看作重复子问题，所以可以使用dfs来解决。
使用深搜来解决这道题也很简单： 1、首先既然需要先遍历到叶子结点，那么就一定是后序遍历，我们可以新建节点记录返回结果。 2、要确保当前节点的下一个节点指向空才能操作，这也就意味着，当前节点的下一个节点就是叶子结点，将当前节点的下一个节点指向自己，最后将当前节点指向空（这样递归到第一层的时候，整个反转后的链表也会指向空了） 3、剩下就是边界条件，为了防止空指针，如果head为空指针直接返回head，并且根据2，当遍历到最后一个节点时，需要返回上一层，所以当当前节点指向空的时候，返回上一层。

代码演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return dfs(head);
    }

    ListNode *dfs(ListNode *head)//把链表看成一棵树，要想反转链表就必须要从叶子结点往上操作
    {
        if(head == nullptr || head -> next == nullptr) return head;

        ListNode *NewHead = dfs(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;

        return NewHead;
    }
};