链表OJ练习(2)

一、分割链表

题目介绍:

思路:创建两个链表,ghead尾插大于x的节点,lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面,将大小链表链接。

          我们需要在创建两个链表指针,指向两个链表的头节点,用这两个指针标记lhead和ghead的尾结点,方便与尾插。

注:极端边界场景:所有值都小于x;   所有值都大于x;  空链表。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/class Partition {
public:ListNode* partition(ListNode* pHead, int x){ListNode* gtail, * ghead, * ltail, * lhead;gtail = ghead = (struct ListNode*)malloc(sizeof(struct ListNode));ltail = lhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){ltail->next = cur;ltail = ltail->next;}else{gtail->next = cur;gtail = gtail->next;}cur = cur->next;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* newhead = lhead->next;free(lhead);free(ghead);return newhead;}
};

 二、回文链表

题目介绍:

思路:先找到中间节点,可以利用快慢指针找到中间节点,然后将中间节点后面的节点翻转,在和中间节点前面的链表依次比较,如果全部相同则是回文链表否则不是。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falst = head;slow = head;while (falst && falst->next){slow = slow->next;falst = falst->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){struct ListNode* next = cur->next;//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}class PalindromeList
{
public:bool chkPalindrome(ListNode* head){//找到中间节点,将中间节点后面的链表翻转,有第一个和中间节点比较,并依次后移,若全部相同,则为回文链表,反之不是。struct ListNode* mid = middleNode(head);struct ListNode* rmid = reverseList(mid);while (rmid && mid){if (rmid->val != head->val){return false;}head = head->next;rmid = rmid->next;}return true;}};

三、找公共点

题目介绍:

思路:先遍历两个链表,计算出两个链表的长度,让后计算出两个链表的长度差k,将长的链表先往前走k步,然后将两个链表指针同时后移,找到第一个相同的节点就是相交节点。

注:需要考虑到空链表,给链表判空,若空headA和headB其中一个为空返回NULL。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 1;int lenB = 1;if(headA==NULL||headB==NULL){return NULL;}while (curA->next){curA = curA->next;lenA++;}while (curB->next){curB = curB->next;lenB++;}if (curA != curB)  //没有交点{return false;}int gap = abs(lenA - lenB);struct ListNode* falst = headA;struct ListNode* slow = headB;if (lenA < lenB){falst = headB;slow = headA;}while (gap--){falst = falst->next;}while (slow != falst){slow = slow->next;falst = falst->next;}return slow;
}

四、判断是否是环形链表

题目介绍:

思路:还是利用快慢指针,当慢指针往前走一步,快指针往前走两步,在一个环中,每次他们的距离就减少一,如果有环,就一定能追上。如果没追上则没有环。

用快指针遍历。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) 
{struct ListNode *falst=head;struct ListNode *slow=head;while(falst&&falst->next){falst=falst->next->next;slow=slow->next;if(falst==slow){return true;}}return false;
}

五、寻找环形链表的入环节点

题目描述:

思路1:假设链表带环,头节点head与入环节点的距离为L,入环节点与相遇点的距离为D,环的大小为C,如下图:

fast从头节点到相遇点:L + D + kC,其中k为正整数,表示在快慢指针相遇前fast所走圈数

slow从头节点到相遇点:L + D

又由于fast每次走两步,slow每次走一步,以上二式可以建立起联系:

L + D + kC = 2 * (L + D)

L = kC - D = (k - 1) * C + C - D     

所以可以得出结论:一个指针从相遇点开始走,一个指针从链表头开始走,则这两个指针一定会在入环节点处相遇。

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head, *slow=head;while(fast && fast->next){fast=fast->next->next;slow = slow->next;if(fast == slow){//找相遇点meetNodestruct ListNode* meetNode = fast;//相遇点可能就是入环节点if(meetNode == head)return head;//meetNode和head开始每次走一步,直到相遇while(head && meetNode){meetNode = meetNode->next;head = head->next;//当相遇时即为入环节点if(meetNode == head)return meetNode;}}}return NULL;
}

思路2:我们可以在相遇点将链表断开,找到如节点就相当于找到两个链表的交点。

找两个链表的交点我们可以参考题目三

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode *curA=headA;struct ListNode *curB=headB;int lenA=1;int lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB)  //没有交点{return false;}int gap=abs(lenA-lenB);struct ListNode *falst=headA;struct ListNode *slow=headB;if(lenA<lenB){falst=headB;slow=headA;}while(gap--){falst=falst->next;}while(slow!=falst){slow=slow->next;falst=falst->next;}return slow;
}
struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode *fast=head;struct ListNode *slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)  //相遇了{struct ListNode *meet=slow;  //将环断开struct ListNode *newhead=meet->next;meet->next=NULL;return getIntersectionNode(head,newhead); //找两个链表的交点}}return NULL;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入了解Docker镜像操作

Docker是一种流行的容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包成容器&#xff0c;以便在不同环境中轻松部署和运行。在Docker中&#xff0c;镜像是构建容器的基础&#xff0c;有些家人们可能在服务器上对docker镜像的操作命令不是很熟悉&#xff0c;本文将深…

Android安卓实战项目(13)---记账APP详细记录每天的收入和支出并且分类统计【生活助手类APP】强烈推荐自己也在用!!!(源码在文末)

Android安卓实战项目&#xff08;13&#xff09;—记账APP详细记录每天的收入和支出并且分类统计【生活助手类APP】强烈推荐自己也在用&#xff01;&#xff01;&#xff01;&#xff08;源码在文末&#x1f415;&#x1f415;&#x1f415;&#xff09; 一.项目运行介绍 B站…

如何确认linux的包管理器是yum还是apt,确认之后安装其他程序的时候就需要注意安装命令

打开终端 输入apt&#xff0c;下图中提示未找到命令&#xff0c;则基本上包管理工具就是用yum的 输入yum&#xff0c;我们看到有打印信息&#xff0c;则说明包管理工具是yum的&#xff0c;离线安装命令使用rpm

MongoDB - 安装

一、Docker安装MongoDB 1. 安装 安装版本: 7.0.0 docker run -itd --name mongodb -v C:\\data\\mongodb\\data:/data/db -p 27017:27017 mongo:7.0.0 --auth-v: 将容器目录/data/db映射到本地C:\\data\\mongodb\\data目录&#xff0c;防止容器删除数据丢失-p: 端口映射--aut…

设计模式-4--原型模式(Prototype Pattern)

一、什么是原型模式 原型模式&#xff08;Prototype Pattern&#xff09;是一种创建型设计模式&#xff0c;它的主要目的是通过复制现有对象来创建新的对象&#xff0c;而无需显式地使用构造函数或工厂方法。这种模式允许我们创建一个可定制的原型对象&#xff0c;然后通过复制…

html5——前端笔记

html 一、html51.1、理解html结构1.2、h1 - h6 (标题标签)1.3、p (段落和换行标签)1.4、br 换行标签1.5、文本格式化1.6、div 和 span 标签1.7、img 图像标签1.8、a 超链接标签1.9、table表格标签1.9.1、表格标签1.9.2、表格结构标签1.9.3、合并单元格 1.10、列表1.10.1、ul无序…

六、vim编辑器的使用

1、编辑器 (1)编辑器就是一款软件。 (2)作用就是用来编辑文件&#xff0c;譬如编辑文字、编写代码。 (3)Windows中常用的编辑器&#xff0c;有自带的有记事本(notepad)&#xff0c;比较好用的notepad、VSCode等。 (4)Linux中常用的编辑器&#xff0c;自带的最古老的vi&…

栈和队列篇

目录 一、栈 1.栈的概念及结构 1.1栈的概念 1.2栈的结构示意图 2.栈的实现 2.1支持动态增长的栈的结构 2.2压栈&#xff08;入栈&#xff09; 2.3出栈 2.4支持动态增长的栈的代码实现 二、队列 1.队列的概念及结构 1.1队列的概念 1.2队列的结构示意图 2.队列的实…

安防监控/视频存储/视频汇聚平台EasyCVR接入海康Ehome车载设备出现收流超时的原因排查

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。视频汇聚平台既具…

uni-app之android项目云打包

1&#xff0c;项目根目录&#xff0c;找到mainfest.json&#xff0c;如果appid是空的&#xff0c;需要生成一个appid 2&#xff0c;点击重新获取appid&#xff0c;这个时候需要登录&#xff0c;那就输入账号密码登录下 3&#xff0c;登陆后可以看到获取appid成功 4&#xff0c;…

四轴飞行器的电池研究(MatlabSimulink仿真)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【力扣每日一题】2023.8.31 一个图中连通三元组的最小度数

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一个无向图&#xff0c;要我们找出三个节点&#xff0c;这三个节点他们两两相连&#xff0c;这三个节点除了连接到对方的其他线…

Windows下Redis的安装

文章目录 一,Redis介绍二,Redis下载三,Redis安装-解压四,Redis配置五,Redis启动和关闭(通过terminal操作)六,Redis连接七,Redis使用 一,Redis介绍 远程字典服务,一个开源的,键值对形式的在线服务框架,值支持多数据结构,本文介绍windows下Redis的安装,配置相关,官网默认下载的是…

QT day1

作业&#xff1a; 编写一个类似图片的 #include "burger.h"burger::burger(QWidget *parent): QWidget(parent) {//设置初始尺寸this->resize(400,320);//设置尺寸最大值最小值this->setMaximumSize(400,320);this->setMinimumSize(400,320);//设置窗口标…

中国行政区域带坐标经纬度sql文件及地点获取经纬度方法

文章目录 前言一、如何获取某地的经纬度&#xff1f;1.1 搜索百度地图1.2 在下方找到地图开放平台1.3 下滑找到坐标拾取器1.4 使用 二、sql文件2.1 创建表2.2 插入数据 前言 当工作业务上需要涉及地图&#xff0c;给前端返回经纬度等场景&#xff0c;需要掌握区域经纬度的获取…

在iPhone 15发布之前,iPhone在智能手机出货量上占据主导地位,这对安卓来说是个坏消息

可以说这是一记重拳&#xff0c;但似乎没有一个有价值的竞争者能与苹果今年迄今为止的智能手机出货量相媲美。 事实上&#xff0c;根据Omdia智能手机型号市场跟踪机构收集的数据&#xff0c;苹果的iPhone占据了前四名。位居榜首的是iPhone 14 Pro Max&#xff0c;2023年上半年…

C# Linq源码分析之Take(四)

概要 本文主要对Take的优化方法进行源码分析&#xff0c;分析Take在配合Select&#xff0c;Where等常用的Linq扩展方法使用时候&#xff0c;如何实现优化处理。 本文涉及到Select, Where和Take和三个方法的源码分析&#xff0c;其中Select, Where, Take更详尽的源码分析&…

iOS开发Swift-3-UI与按钮Button-摇骰子App

1.创建新项目Dice 2.图标 删去AppIcon&#xff0c;将解压后的AppIcon.appiconset文件拖入Assets包。 3.将素材点数1-6通过网页制作成2x&#xff0c;3x版本并拖入Asset。 4.设置对应的UI。 5.拖入Button组件并设置style。 6.Ctrl加拖拽将Button拖拽到ViewController里&#xff0…

WPF实战项目十三(API篇):备忘录功能api接口、优化待办事项api接口

1、新建MenoDto.cs /// <summary>/// 备忘录传输实体/// </summary>public class MemoDto : BaseDto{private string title;/// <summary>/// 标题/// </summary>public string Title{get { return title; }set { title value; OnPropertyChanged();…

Day5:react函数组件与类组件

「目标」: 持续输出&#xff01;每日分享关于web前端常见知识、面试题、性能优化、新技术等方面的内容。 「主要面向群体&#xff1a;」前端开发工程师&#xff08;初、中、高级&#xff09;、应届、转行、培训、自学等同学 Day4-今日话题 react「函数组件和类组件」的区别&…