算法随想录第四天打卡|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交 ,142.环形链表II

本文主要是介绍算法随想录第四天打卡|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交 ,142.环形链表II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

24. 两两交换链表中的节点

用虚拟头结点,这样会方便很多。 

本题链表操作就比较复杂了,建议大家先看视频,视频里我讲解了注意事项,为什么需要temp保存临时节点。

题目链接/文章讲解/视频讲解: 代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headdummy_head=ListNode(next=head)current=dummy_headwhile current.next and current.next.next:temp=current.nexttemp1=current.next.next.nextcurrent.next=temp.nexttemp.next.next=temptemp.next=temp1current=current.next.nextreturn dummy_head.next

C++

/*** 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* swapPairs(ListNode* head) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* current=dummy_head;while (current->next && current->next->next){ListNode* temp1=current->next;ListNode* temp2=current->next->next->next;current->next=temp1->next;temp1->next->next=temp1;temp1->next=temp2;current=current->next->next;}ListNode* temp=dummy_head->next;delete dummy_head;return temp;}
};

总结

下次要把临时节点写在循环里面,作为一个变量放在外面显得代码量很多。

19.删除链表的倒数第N个节点

双指针的操作,要注意,删除第N个节点,那么我们当前遍历的指针一定要指向 第N个节点的前一个节点,建议先看视频。

题目链接/文章讲解/视频讲解:代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy_head=ListNode(next=head)slow,fast=dummy_head,dummy_headfor i in range(n):fast=fast.nextwhile fast.next:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturn dummy_head.next

C++

/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* fast=dummy_head;ListNode* slow=dummy_head;for (int i=0;i<n;i++)fast=fast->next;while (fast->next){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return dummy_head->next;}
};

面试题 02.07

本题没有视频讲解,大家注意 数值相同,不代表指针相同。

题目链接/文章讲解:代码随想录

Python

/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* fast=dummy_head;ListNode* slow=dummy_head;for (int i=0;i<n;i++)fast=fast->next;while (fast->next){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return dummy_head->next;}
};

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* cura=headA;ListNode* curb=headB;int lena=0,lenb=0;while (cura){cura=cura->next;lena++;}while (curb){curb=curb->next;lenb++;}if (lena>lenb){for (int i=0;i<lena-lenb;i++)headA=headA->next;}else{for (int i=0;i<lenb-lena;i++)headB=headB->next;}while (headA){if (headA==headB) return headA;headA=headA->next;headB=headB->next;}return nullptr;}
};

142.环形链表II

算是链表比较有难度的题目,需要多花点时间理解 确定环和找环入口,建议先看视频。

题目链接/文章讲解/视频讲解:代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast,slow=head,headwhile fast and fast.next:fast=fast.next.nextslow=slow.nextif fast==slow: slow=headwhile slow!=fast:slow=slow.nextfast=fast.nextreturn fastreturn None

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast=head;ListNode* slow=head;while (fast && fast->next){fast=fast->next->next;slow=slow->next;if (fast==slow){slow=head;while (slow!=fast){slow=slow->next;fast=fast->next;}return fast;}}return nullptr;}
};

总结

都还写出来了,没有忘记,说明一刷的时候掌握还行。

这篇关于算法随想录第四天打卡|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交 ,142.环形链表II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978618

相关文章

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

python删除xml中的w:ascii属性的步骤

《python删除xml中的w:ascii属性的步骤》使用xml.etree.ElementTree删除WordXML中w:ascii属性,需注册命名空间并定位rFonts元素,通过del操作删除属... 可以使用python的XML.etree.ElementTree模块通过以下步骤删除XML中的w:as

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

如何在Mac上彻底删除Edge账户? 手动卸载Edge浏览器并清理残留文件技巧

《如何在Mac上彻底删除Edge账户?手动卸载Edge浏览器并清理残留文件技巧》Mac上的Edge账户里存了不少网站密码和个人信息,结果同事一不小心打开了,简直尴尬到爆炸,想要卸载edge浏览器并清... 如果你遇到 Microsoft Edge 浏览器运行迟缓、频繁崩溃或网页加载异常等问题,可以尝试多种方

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略(Key Expir