数据结构初阶leetcodeOJ题(二)

目录

第一题

 思路:

第二题

 思路

 第三题

描述

示例1

 思路

总结:这种类似的题,都是用快慢指针,相差一定的距离然后输出慢指针。


第一题

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

 方法一

思路:

快慢指针:一个指向目标结点,一个指向目标结点的前驱结点。用一个tmp保存pos->next.

                  free()掉目标结点。

分两种情况:如果只有一个节点或者要删除的结点是首元节点,那么这时pre为NULL,pos                       指向pos;否则pre->next == pos;

 

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* pre = NULL;
    struct ListNode* pos = head;
    while(pos!=NULL)
    {
        if(pos->val==val){
            struct ListNode* tmp = pos->next;
            free(pos);
            pos = tmp;
            if(pre==NULL){
                head = pos;
            }else{
                pre->next = pos;
            }
        }
        else
        {
            pre = pos;
            pos = pos->next;
        }
    }
    return head;
}

方法二: 

思想;

创建新链表,用尾插法,尾插法没有改变原指针的next指向所以不用保存next节点,

但是在free()时要保存下一节点。

 

struct ListNode* removeElements(struct ListNode* head, int val)
{

    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;
    while(cur!=NULL)
    {
        if(cur->val!=val)
        {
            if(newhead==NULL){
                newhead = tail = cur;
            }else{
                tail->next = cur;
                tail = cur;
            }
            cur = cur->next;

        }else{
            struct ListNode* tmp = cur ->next;
            free(cur);
            cur = tmp;
        }
    }
    if(tail)
        tail->next=NULL;

    return newhead;

}

 

 

第二题

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。

示例 2:

输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

 思路

用快慢指针:快指针一次走两个,慢指针一次走一个。这样他们的路程之间差二倍。所以输出慢指针,即输出中间节点。

 

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow = slow ->next;
        fast = fast->next->next;
    }
    return slow;
}

 第三题

描述

输入一个链表,输出该链表中倒数第k个结点。

示例1

输入:

1,{1,2,3,4,5}

复制返回值:

{5}

 思路

用快慢指针:快指针比慢指针先走k步,然后两者在同时走。

 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* pre =pListHead;
    struct ListNode* pos = pListHead;
    while(k--){
        if(pos!=NULL){
        pos = pos->next;
        }else{
            return NULL;
        }
 
    }
    while(pos!=NULL){
 
        pre = pre->next;
        pos = pos->next;
 
    }
    return pre;
 
}

总结:这种类似的题,都是用快慢指针,相差一定的距离然后输出慢指针。

第四题 

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

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

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

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

 方法一

 将节点之间的next翻转。

用三个指针的原因是,只用两个指针翻转时,会导致链表断裂,但是用第三个指针保存下一个节点这样链表就不会断裂。

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //方法一
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
        return NULL;
    struct ListNode* left = NULL;
    struct ListNode* right= head;
    struct ListNode* tmp = head->next;
    while(right!=NULL)
    {

        right->next = left;
        left = right;
        right = tmp;
        if(tmp!=NULL)
        tmp = tmp->next;
    }

    return left;
}

方法二 

用头插法,注意头插法需要保存指针。尾插法不用保存指针。

错误总结

 

(1)注意头插是新结点指向头结点,然后在将新节点设置为头结点。而不是直接将新节点设置为头节点 

(2)C语言赋值语句,左值是变量,将新节点设置为头结点。newnode = cur;这是头结点为cur

 

//方法二
struct ListNode* reverseList(struct ListNode* head) 
{
   if(head==NULL)
        return NULL;
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur!=NULL)
    {

        struct ListNode* next = cur ->next; //保存下一个
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162916.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2023全新付费进群系统源码 带定位完整版 附教程

这源码是我付费花钱买的分享给大家&#xff0c;功能完整。 搭建教程 Nginx1.2 PHP5.6-7.2均可 最好是7.2 第一步上传文件程序到网站根目录解压 第二步导入数据库&#xff08;58soho.cn.sql&#xff09; 第三步修改/config/database.php里面的数据库地址 第四步修改/conf…

【漏洞复现】泛微e-Weaver SQL注入

漏洞描述 泛微e-Weaver&#xff08;FANWEI e-Weaver&#xff09;是一款广泛应用于企业数字化转型领域的集成协同管理平台。作为中国知名的企业级软件解决方案提供商&#xff0c;泛微软件&#xff08;广州&#xff09;股份有限公司开发和推广了e-Weaver平台。 泛微e-Weaver旨在…

LeetCode(28)盛最多水的容器【双指针】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 盛最多水的容器 1.题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水…

Java中如何通过路径表达式找值:XPath和JsonPath以及SpEL详解及对比

大家好&#xff0c;我是G探险者。 我们编程时&#xff0c;在前后端数据交互和传输过程中&#xff0c;往往需要对报文中的某个字段或者某个标签的值进行解析读取&#xff0c;报文通常是以json或者xml作为数据交换格式&#xff0c;而json和xml这两种格式的报文结构都是具备一定的…

CI/CD -gitlab

目录 一、常用命令 二、部署 一、常用命令 官网&#xff1a;https://about.gitlab.com/install/ gitlab-ctl start # 启动所有 gitlab 组件 gitlab-ctl stop # 停止所有 gitlab 组件 gitlab-ctl restart # 重启所有 gitlab 组件 gitlab-ctl statu…

比Postman强在哪里

Postman的受众对象主要是广大开发人员&#xff0c;调测使用&#xff0c;它并不能完全满足专业测试人员需求&#xff0c;而自动化测试平台可以 1&#xff0c;Postman&#xff0c;Jmter是单机版软件&#xff0c;类似打游戏你和电脑PK&#xff0c;而很多时候是要联网和其他人团队作…

软件开发、网络空间安全、人工智能三个方向的就业和前景怎么样?哪个方向更值得学习?

软件开发、网络空间安全、人工智能这三个方向都是当前及未来的热门领域&#xff0c;每个领域都有各自的就业前景和价值&#xff0c;以下是对这三个方向的分析&#xff1a; 1、软件开发&#xff1a; 就业前景&#xff1a;随着信息化的加速&#xff0c;软件开发的需求日益增长。…

【PyQt小知识 - 3】: QComboBox下拉框内容的设置和更新、默认值的设置、值和下标的获取

QComboBox 内容的设置和更新 from PyQt5.QtWidgets import * import sysapp QApplication(sys.argv)mainwindow QMainWindow() mainwindow.resize(200, 200) # 设置下拉框 comboBox QComboBox(mainwindow) comboBox.addItems([上, 中, 下])button QPushButton(更新, main…

Django学习日志03

数据的增删改查&#xff08;insert update delete select&#xff09; 1. 用户列表的展示 # 把数据表中得用户数据都给查询出来展示在页面上 添加数据 id username password gender age action …

Web与DNS综合实验

目录 题目&#xff1a; 步骤一&#xff1a;准备工作 步骤二&#xff1a;在server端搭建简单网页 步骤三&#xff1a;node1端的DNS解析配置 步骤五&#xff1a;node2端进行测试。 题目&#xff1a; 1.打开3个主机&#xff0c;server、node1、node2 2.server为web主机建立网…

如何将 Docsify 项目部署到 CentOS 系统的 Nginx 中?

文章目录 1. 介绍2. 准备工作3. 将 Docsify 项目上传至服务器4. 在服务器上安装 Node.js5. 在服务器上运行 Docsify6. 配置 Nginx 反向代理7. 访问 Docsify 文档8. 拓展8.1 配置 HTTPS8.2 定制 Docsify 主题8.3 鉴权和访问控制 &#x1f389;如何将 Docsify 项目部署到 CentOS …

​软考-高级-系统架构设计师教程(清华第2版)【第20章 系统架构设计师论文写作要点(P717~728)-思维导图】​

软考-高级-系统架构设计师教程&#xff08;清华第2版&#xff09;【第20章 系统架构设计师论文写作要点&#xff08;P717~728&#xff09;-思维导图】 课本里章节里所有蓝色字体的思维导图

图片标注工具Labelme的安装及使用方法

参考&#xff1a;图像语义分割标注工具labelme制作自己的数据集用于mask-rcnn训练_ZealCV的博客-CSDN博客_语义分割标注工具 在做目标检测任务时&#xff0c;需要用到labelImg进行画框标注&#xff0c;在之前的文章中已经介绍过该工具的使用方法。然而如果是做语义分割的任务时…

Linux命令之查看文件和权限修改操作

目录 查看文件 1. cat --- 将文件中的内容打印在输出设备 2. more --- 分页显示文件内容 3.less ---查看文件内容 4. head -- 查看文件前n行内容 5.tail -- 查看指定文件的后n行内容或实时监测文件 6. wc -- 可计算文件的字节数、字数和列数 文件搜索 1.which --- 获取…

大数据可视化是什么?

大数据可视化是将海量数据通过视觉方式呈现出来&#xff0c;以便于人们理解和分析数据的过程。它可以帮人们发现数据之间的关系、趋势和模式&#xff0c;并制定更明智的决策。大数据可视化通常通过图形、图表、地图和仪表盘等视觉元素来呈现数据。这些元素具有直观、易理解的特…

Prompt 编程的设计技巧

大家好&#xff0c;我是木川 《Prompt 编程》即利用 GPT 模型的能力实现编程效果&#xff0c;《Prompt 编程》最早是由菠菜老师提出&#xff0c;本文基于 《Prompt 编程》的概念及自己的一些感想&#xff0c;总结了下《 Prompt 编程》的设计技巧 一、结构化 针对复杂的 Prompt&…

sqli-labs(2)

7. 输入?id1 --显示格式错误 ?id1" --正常 测试 ?id1“ and sleep(5) -- 发现并没有成功 ?id1) --显示格式错误继续尝试 ?id1)) -- 显示正常 测试 ?id1“ and sleep(5) -- 发现sleep执行 对于语句闭合的尝试主要从 " ()来测试 报错语句尝试发现不回显报错信息…

Solidity基础语法代码2

// SPDX-License-Identifier: MIT pragma solidity ^0.8.0; /* 哈希算法具有两个特性&#xff1a; 1. 输入值相同&#xff0c;输出值一定相同 2. 不管输入值有多大&#xff0c;输出值是定长的&#xff0c;并且哈希算法是不可逆向运算的 通常把哈希算法用在签名运算&#xff0…

在网页中添加水印的实现方法

在网页设计中&#xff0c;为了保护内容的版权以及增加一些特殊效果&#xff0c;经常需要在页面上添加水印。本文将介绍一种通过Canvas和JavaScript实现在网页上添加水印的方法。 功能&#xff1a; 允许自定义水印内容、字体颜色可以防止用户删除水印元素、修改样式等其他手段…

基于原子搜索算法优化概率神经网络PNN的分类预测 - 附代码

基于原子搜索算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于原子搜索算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于原子搜索优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…