【数据结构与算法 | 基础篇】[链表专题]力扣21, 234

简介: 【数据结构与算法 | 基础篇】[链表专题]力扣21, 234

1. 力扣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 均按 非递减顺序 排列

思路 :双指针

先判断list1,list2是否为空的三种情况,再按照双指针法依次将两个链表串起来.head记录头指针的位置.p指针起到串联的作用.

解 :

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode p;
        if (list1.val > list2.val) {
            p = list2;
            list2 = list2.next;
        } else {
            p = list1;
            list1 = list1.next;
        }
        ListNode head = p;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                p.next = list2;
                p = p.next;
                list2 = list2.next;
            } else {
                p.next = list1;
                p = p.next;
                list1 = list1.next;
            }
        }
        if (list1 == null) {
            p.next = list2;
        } else {
            p.next = list1;
        }
        return head;
    }
}

2. 力扣234 : 回文链表

题 :

给你一个单链表的头节点 head ,请你判断该链表是否为
回文链表
。如果是,返回 true ;否则,返回 false 。
 
 
 
示例 1:
 
 
输入:head = [1,2,2,1]
输出:true
示例 2:
 
 
输入:head = [1,2]
输出:false
 
 
提示:
 
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
 
 
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

思路 : 辅助数组 + 双指针

借助辅助数组,从而判断数组是否是回文数组.该解法空间复杂度较高O(n).但时间复杂度为O(n).

解 :

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode p = head;
        int count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }
        int[] a = new int[count];
        p = head;
        count = 0;
        while (p != null) {
            a[count++] = p.val;
            p = p.next;
        }
        boolean flag = true;
        int last = count - 1;
        int hed = 0;
        for (int i = count / 2; i > 0; i--) {
            if (a[hed++] != a[last--]) {
                flag = false;
            }
        }
        return flag;
    }
}
目录
打赏
0
1
0
0
7
分享
相关文章
|
8月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
134 4
|
3月前
|
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
117 10
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
78 0
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
147 30
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
210 25
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
277 5
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
195 5
|
8月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
180 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等