合并有序链&&反转链表(递归版)

简介: 合并有序链&&反转链表(递归版)

每日一题系列(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;
    }
};

总结

  递归逻辑三步走,首先看时候能拆分成重复子问题,再看如何执行递归,最后别忘记结束递归的边界条件!

  虽然题目很简单,但是以递归的方式解决还是可以很好的锻炼我们的递归逻辑思维的,总得要一步一个脚印,慢慢的啃下这块硬骨头。

相关文章
|
7月前
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
46 0
|
7月前
|
算法
算法系列--递归(一)--与链表有关(上)
算法系列--递归(一)--与链表有关
69 0
|
6月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
7月前
|
算法
算法系列--递归(一)--与链表有关(下)
算法系列--递归(一)--与链表有关(下)
37 0
|
7月前
|
存储 算法 C语言
【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫
【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫
力扣203移除链表元素:思路分析+代码实现+方法总结(伪头节点法&递归)
力扣203移除链表元素:思路分析+代码实现+方法总结(伪头节点法&递归)
107 0
|
7月前
|
算法
每日一题——排序链表(递归 + 迭代)
每日一题——排序链表(递归 + 迭代)
|
7月前
【每日一题Day286】LC21合并两个有序链表 | 链表模拟 递归
【每日一题Day286】LC21合并两个有序链表 | 链表模拟 递归
34 0
|
算法
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
92 0
C++递归解决两两交换链表中节点
C++递归解决两两交换链表中节点