【面试高频系列】既能考察对「数据结构」的掌握,还能考察对「递归函数」的设计 ... |刷题打卡

简介: 【面试高频系列】既能考察对「数据结构」的掌握,还能考察对「递归函数」的设计 ... |刷题打卡

题目描述



这是 LeetCode 上的24. 两两交换链表中的节点,难度为 Medium。


给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。


你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。


示例 1:


网络异常,图片无法展示
|


输入:head = [1,2,3,4]
输出:[2,1,4,3]
复制代码


示例 2:


输入:head = []
输出:[]
复制代码


示例 3:


输入:head = [1]
输出:[1]
复制代码


提示:


  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100


递归解法(哨兵技巧)



哨兵技巧我们之前在前面的多道链表题讲过,让三叶来帮你回忆一下:


做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。


链表和树的题目天然适合使用递归来做。


我们可以设计一个递归函数,接受一个 ListNode 节点 root 作为参数,函数的作用是将 root 后面的两个节点进行交换,交换完成后再将下一个节点传入 ...


交换的前提条件:节点 root 后面至少有两个节点。同时别忘了应用我们的「哨兵技巧」:


代码:


class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        recursive(dummy);
        return dummy.next;
    }
    // 函数的作用是将 root 后面的两个节点进行互换
    void recursive(ListNode root) {
        if (root.next != null && root.next.next != null) {
            ListNode a = root.next, b = a.next;
            root.next = b;
            a.next = b.next;
            b.next = a;
            recursive(a);
        }
    }
}
复制代码


  • 时间复杂度:会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


迭代解法(哨兵技巧)



所有的递归都能转化为迭代:


class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for (ListNode cur = dummy; cur.next != null && cur.next.next != null;) {
            ListNode a = cur.next, b = a.next;
            cur.next = b;
            a.next = b.next;
            b.next = a;
            cur = a;
        }
        return dummy.next;
    }
}
复制代码


  • 时间复杂度:会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.24 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
200 3
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
11月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
202 4
|
12月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
133 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
12月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
309 1
|
12月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
137 4
|
11月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
机器学习/深度学习
【机器学习】如何判断函数凸或非凸?(面试回答)
文章介绍了如何判断函数是凸函数还是非凸函数,包括凸函数的定义、几何意义、判定方法(一元函数通过二阶导数判断,多元函数通过Hessian矩阵的正定性判断),以及凸优化的概念和一些经典的凸优化问题。
926 1
【机器学习】如何判断函数凸或非凸?(面试回答)
|
12月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
241 0