企业网站建设哪家好,网页设计专业,网站后台英文,免费建微网站Python蓝桥杯训练#xff1a;基本数据结构 [链表] 文章目录Python蓝桥杯训练#xff1a;基本数据结构 [链表]一、链表理论基础知识二、有关链表的一些常见操作三、力扣上面一些有关链表的题目练习1、[移除链表元素](https://leetcode.cn/problems/remove-linked-list-element…Python蓝桥杯训练基本数据结构 [链表] 文章目录Python蓝桥杯训练基本数据结构 [链表]一、链表理论基础知识二、有关链表的一些常见操作三、力扣上面一些有关链表的题目练习1、[移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/)2、[设计链表](https://leetcode.cn/problems/design-linked-list/)3、[反转链表](https://leetcode.cn/problems/reverse-linked-list/)4、[两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)5、[删除链表的倒数第N个节点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)6、[相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/)7、[环形链表Ⅱ](https://leetcode.cn/problems/linked-list-cycle-ii/)本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、链表理论基础知识
链表是一种特殊的数据结构它是由节点node组成的。每个节点都存储了一个数据元素和一个指向下一个节点的指针。指向最后一个节点的指针是空的。因此我们可以从第一个节点开始通过沿着指针移动到下一个节点直到到达最后一个节点为止。
链表有两种类型单向链表和双向链表。在单向链表中每个节点只指向下一个节点而在双向链表中每个节点都指向下一个节点和前一个节点。
链表具有动态内存分配因此我们可以在不需要预先知道链表大小的情况下在链表中插入或删除元素。
在 Python 中我们可以使用类来实现链表。每个节点可以是一个类的实例其中包含数据元素和指向下一个节点的指针。
操作链表的常见任务包括插入节点、删除节点、查找节点、遍历链表等。
常用的链表操作有单链表、双向链表、循环链表、双向循环链表等。
下面我们来简单的介绍一下单链表、双向链表、循环链表、双向循环链表
单链表在单链表中每个节点只包含一个指向下一个节点的指针。指向最后一个节点的指针是空的。双向链表在双向链表中每个节点都包含一个指向下一个节点的指针和一个指向前一个节点的指针。循环链表在循环链表中最后一个节点的指针不是空的而是指向第一个节点。因此我们可以从任何节点开始通过沿着指针移动到下一个节点直到回到第一个节点为止。双向循环链表双向循环链表是循环链表的双向版本即每个节点都包含一个指向下一个节点的指针和一个指向前一个节点的指针并且最后一个节点的指针指向第一个节点第一个节点的指针指向最后一个节点。
二、有关链表的一些常见操作 插入在链表的任意位置插入新节点 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 在指定位置插入一个新节点def insert_at_pos(self, pos, data):# 创建一个节点new_node Node(data)# 如果链表为空if self.head is None:self.head new_nodereturn# 如果位置为0则在开头插入if pos 0:new_node.next self.headself.head new_nodereturn# 遍历链表找到位置temp self.headcount 0while temp is not None:if count pos - 1:breaktemp temp.nextcount 1# 插入节点new_node.next temp.nexttemp.next new_node删除从链表中删除指定的节点 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 删除指定数据的节点def delete_node(self, data):# 如果链表为空if self.head is None:return# 如果头节点有数据if self.head.data data:self.head self.head.nextreturn# 遍历链表temp self.headwhile temp.next is not None:if temp.next.data data:breaktemp temp.next# 删除节点if temp.next is not None:temp.next temp.next.next查询查询链表中指定元素的位置 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 找到指定数据的位置def find_pos(self, data):# 如果链表为空if self.head is None:return -1# 遍历链表temp self.headcount 0while temp is not None:if temp.data data:return counttemp temp.nextcount 1# 元素未找到return -1修改修改链表中指定元素的值
# 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 更新指定位置的节点def update_at_pos(self, pos, data):# 如果链表为空if self.head is None:return#遍历链表找到位置temp self.headcount 0while temp is not None:if count pos:breaktemp temp.nextcount 1#更新节点if temp is not None:temp.data data遍历从头到尾遍历整个链表 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 遍历链表def traverse(self):temp self.headwhile temp is not None:print(temp.data)temp temp.next计数计算链表中节点的数量 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 统计链表中节点的个数def count_nodes(self):temp self.headcount 0while temp is not None:count 1temp temp.nextreturn count排序对链表中的元素进行排序 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 对链表进行排序def sort_linked_list(self):temp self.headwhile temp is not None:current tempwhile current.next is not None:if current.data current.next.data:current.data, current.next.data current.next.data, current.datacurrent current.nexttemp temp.next反转将链表中的元素反转 # 节点类
class Node:def __init__(self, data):self.data dataself.next None# 链表类
class LinkedList:def __init__(self):self.head None# 反转链表def reverse(self):prev Nonecurrent self.headwhile current is not None:next current.nextcurrent.next prevprev currentcurrent nextself.head prev三、力扣上面一些有关链表的题目练习
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
输出[]提示
列表中的节点数目在范围 [0, 104] 内
1 Node.val 50
0 val 50这道题属于链表的基本操作在上面介绍链表的常用方法时就提到了如何删除链表的元素上面的方法是需要判断删除元素是否是链表头节点也就是说删除头节点很删除其他节点的方法是不一样的这是因为链表的其他节点都是通过前一格节点来移除当前节点而头节点没有前一个节点所以需要分开讨论那么有没有一种统一的方法进行删除呢当然我们可以通过给原先链表设置一个虚拟头节点这样原链表的所有节点就可以统一进行删除了。 那么什么是虚拟节点呢
虚拟节点dummy node是在链表头部创建一个不存储任何数据的特殊节点用来解决链表操作问题。通常情况下在链表头部插入或移除元素时需要特殊处理以避免对链表头部的直接操作。使用虚拟节点可以在链表头部插入和移除元素时统一处理从而简化代码。 ✍ 我们知道了要使用虚拟节点来进行链表的删除操作具体的代码实现如下 # Definition for singly-linked list.
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:def removeElements(self, head: ListNode, val: int) - ListNode:dummy ListNode(0)dummy.next headprev dummycurrent headwhile current:if current.val val:prev.next current.nextelse:prev currentcurrent current.nextreturn dummy.next上述代码的具体实现思路如下
创建一个虚拟节点该节点的值不重要只是用来作为链表的头部。创建两个指针一个指向虚拟节点prev一个指向链表头current。在链表中遍历每一个节点如果该节点的值等于给定值val则将prev的next指向该节点的下一个节点即跳过该节点。如果该节点的值不等于给定值val则将prev指向该节点。遍历完整个链表后返回虚拟节点的next。 ⚠️ 在解决上面题目时我们应该注意以下几点 链表的遍历顺序确保指针正确的遍历链表的每一个节点。变量的更新确保在遍历每一个节点时更新prev和current的值。虚拟节点的初始化创建一个虚拟节点并且初始化它的next值为链表头。返回值确保返回虚拟节点的next而不是链表头。
如何要对上述代码进行示例测试的话需要注意这跟之前的数组不一样具体例子如下
head ListNode(1)
head.next ListNode(2)
head.next.next ListNode(6)
head.next.next.next ListNode(3)
head.next.next.next.next ListNode(4)
head.next.next.next.next.next ListNode(5)
head.next.next.next.next.next.next ListNode(6)
a Solution()
result a.removeElements(head, 6)
node result
while node:print(node.val, end )node node.nextB站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 2、设计链表 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性val 和 next。val 是当前节点的值next 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。 在链表类中实现这些功能
get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点
示例
MyLinkedList linkedList new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1- 2- 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1- 3
linkedList.get(1); //返回3提示
0 index, val 1000
请不要使用内置的 LinkedList 库。
get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次数不超过 2000。这道题相当于将前面的基础知识进行整合考察我们对链表的操作在这里我们方便起见还是继续使用虚拟头节点这样可以对所有节点进行统一操作。 其中get(index)实现思路是
先判断给定的索引index是否合法即是否小于0或大于链表的长度如果不合法返回-1。定义一个当前节点cur并将其设为头节点的下一个节点即链表的第一个节点。进入循环当index不为0时cur更新为其下一个节点index减1。当循环结束后cur的val属性即为所需要的值返回该值。
其中addAtHead(val)实现思路是
创建新节点并设置其值。将新节点的next指针指向当前的链表头部。将新节点设为链表头部。更新链表的大小。
其中addAtTail(val)实现思路是
创建新节点并设置其值。创建当前指针从链表头开始循环直到找到链表的末尾。将新节点添加到末尾。更新链表的大小。
其中addAtIndex实现思路是
检查给定索引是否小于0或大于链表的大小如果是返回-1。创建新节点并设置其值。创建当前指针从链表头开始循环直到找到给定索引处的节点的前一个节点。将新节点的next指针指向给定索引处的节点。将前一个节点的next指针指向新节点。更新链表的大小。
其中deleteAtIndex(index)实现思路是
检查给定索引是否小于0或大于等于链表的大小如果是则返回。否则创建一个当前指针并从链表头开始循环直到找到给定索引前一个节点。删除该节点并更新链表的大小。 ✍ 上述是使用单链表实现的具体实现代码如下 class Node(object):def __init__(self, x0):self.val xself.next Noneclass MyLinkedList(object):def __init__(self):self.head Node()self.size 0 # 设置一个链表长度的属性便于后续操作注意每次增和删的时候都要更新def get(self, index)::type index: int:rtype: intif index 0 or index self.size:return -1cur self.head.nextwhile(index):cur cur.nextindex - 1return cur.valdef addAtHead(self, val)::type val: int:rtype: Nonenew_node Node(val)new_node.next self.head.nextself.head.next new_nodeself.size 1def addAtTail(self, val)::type val: int:rtype: Nonenew_node Node(val)cur self.headwhile(cur.next):cur cur.nextcur.next new_nodeself.size 1def addAtIndex(self, index, val)::type index: int:type val: int:rtype: Noneif index 0:self.addAtHead(val)returnelif index self.size:self.addAtTail(val)returnelif index self.size:returnnode Node(val)pre self.headwhile(index):pre pre.nextindex - 1node.next pre.nextpre.next nodeself.size 1def deleteAtIndex(self, index)::type index: int:rtype: Noneif index 0 or index self.size:returnpre self.headwhile(index):pre pre.nextindex - 1pre.next pre.next.nextself.size - 1 这道题目我们还可以使用双向链表来实现具体的实现过程连同代码我放在下面 # 双链表
# 相对于单链表, Node新增了prev属性
class Node:def __init__(self, val):# 存储节点的值self.val val# 指向前一个节点self.prev None# 指向下一个节点self.next None# 双链表的实现
class MyLinkedList:def __init__(self):# 虚拟节点存储的值可以是0或者任意值self._head, self._tail Node(0), Node(0) # 虚拟节点的前一个节点和后一个节点都是自己self._head.next, self._tail.prev self._tail, self._head# 添加的节点数self._count 0 def _get_node(self, index: int) - Node:# 当index小于_count//2时, 使用_head查找更快, 反之_tail更快if index self._count // 2:# 使用prev往前找node self._tailfor _ in range(self._count - index):node node.prevelse:# 使用next往后找node self._head for _ in range(index 1):node node.next# 返回找到的节点return nodedef get(self, index: int) - int:获取链表中第 index 个节点的值。如果索引无效则返回 -1。# 如果index是合法的即在0和_count-1的范围内if 0 index self._count:# 找到对应的节点node self._get_node(index)# 返回该节点的值return node.valelse:# 如果index不合法返回-1return -1def addAtHead(self, val: int) - None:在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。# 调用_update方法并传入链表的头节点头节点的下一个节点以及要插入的值valself._update(self._head, self._head.next, val)def addAtTail(self, val: int) - None:将值为 val 的节点附加到链表的最后一个元素。# 调用_update方法并传入链表的尾节点的前一个节点尾节点以及要插入的值valself._update(self._tail.prev, self._tail, val)def addAtIndex(self, index: int, val: int) - None:在链表的第 index 个节点之前添加一个值为 val 的节点。如果索引等于链表的长度则该节点将追加到链表的末尾。如果索引大于长度则不会插入该节点。# 如果索引小于0则将索引设置为0如果索引大于链表长度则直接返回if index 0:index 0elif index self._count:return# 获取索引对应的节点node self._get_node(index)# 调用_update方法并传入该节点的前一个节点该节点以及要插入的值valself._update(node.prev, node, val)def _update(self, prev: Node, next: Node, val: int) - None:更新节点:param prev: 相对于更新的前一个节点:param next: 相对于更新的后一个节点:param val: 要添加的节点值# 计数累加self._count 1# 创建一个新节点node Node(val)# 设置前后节点的指向prev.next, next.prev node, nodenode.prev, node.next prev, nextdef deleteAtIndex(self, index: int) - None:如果索引有效则删除链表中的第 index 个节点。# 如果 index 有效if 0 index self._count:# 获取 index 节点node self._get_node(index)# 计数-1self._count - 1# 将前后节点的指向跳过该节点node.prev.next, node.next.prev node.next, node.prevB站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 3、反转链表 给你单链表的头节点 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指针的指向就可以直接将链表反转 而不用重新定义一个新的链表具体实现的方法有两种 使用递归的方法从链表的最后一个节点开始递归每次递归都把当前节点的 next 指向前一个节点最后返回新的头节点。使用循环的方法通过循环每次取出当前节点并把当前节点的 next 指向前一个节点最后把头节点指向最后一个节点。
递归的代码实现会非常的简洁但是有时候会很难理解每一步的含义所以我们可以先尝试使用第二种循环的方法也就是使用双指针的方法反转链表。 ✍ 用双指针实现的思路为 创建两个指针 pre 和 curpre 指向当前节点的前一个节点cur 指向当前节点。使用 cur.next 来移动 cur同时使用 pre 和 cur 实现反转。在每一轮循环中cur 移动到下一个节点pre 指向当前节点cur.next 指向 pre。循环结束后链表的头和尾已经反转。返回新的链表头即原来的链表尾。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def reverseList(self, head: ListNode) - ListNode:prev Nonecurr headwhile curr:next_node curr.nextcurr.next prevprev currcurr next_nodereturn prev相比于双指针递归的代码会更加简洁下面是用递归的方法实现 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def reverseList(self, head: ListNode) - ListNode:# 终止条件当前节点为空或当前节点的下一个节点为空if not head or not head.next:return head# 先递归到最后一个节点让最后一个节点的下一个节点指向前一个节点new_head self.reverseList(head.next)head.next.next headhead.next None# 返回新的头节点return new_head我们还可以在原函数reverseList里面自己定义一个反转函数实现反转操作具体实现过程如下
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: ListNode) - ListNode:反转单链表:param head: 链表的头节点:return: 反轮后的链表头节点def reverse(pre, cur):递归函数每次传入前一个节点和当前节点反转链表:param pre: 前一个节点:param cur: 当前节点:return: 反转后的链表头节点if not cur:# 当前节点为空说明已经到达末尾返回前一个节点return pre# 保存当前节点的下一个节点tmp cur.next# 反转链表当前节点的下一个节点指向前一个节点cur.next pre# 递归下一个节点return reverse(cur, tmp)# 从head开始pre为Nonereturn reverse(None, head)B站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1nB4y1i7eL/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 4、两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例1 输入head [1,2,3,4]
输出[2,1,4,3]示例2
输入head []
输出[]示例3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内
0 Node.val 100这道题需要我们将链表中两两相邻的节点进行交换并返回最后交换后的链表两两交换并不是简单的交换节点的值而是需要改变实际的节点顺序。而且我们还需要考虑链表的节点数是奇数还是偶数的条件所以循环迭代的终止条件是当循环迭代到链表为空或者链表只剩一个元素的时候停止迭代实现的方法有两种方法 递归实现通过递归的方式对链表进行交换并在递归过程中更新节点的指向。迭代实现通过迭代的方式对链表进行交换通过不断更新节点的指向实现交换。
和上面的反转链表题目操作类似我们还是先使用双指针迭代实现然后再用递归的方法实现。 ✍ 使用虚拟节点双指针迭代的方法实现 定义一个虚拟节点dummy其next指向head。定义一个指针pre指向dummy表示要交换的前一个节点。循环条件为pre的next指向的节点不为空且该节点的下一个节点也不为空。定义指针cur指向pre的next指向的节点定义指针post指向cur的next指向的节点。交换cur和post两个节点cur的next指向post的next指向的节点post的next指向cur。将pre的next指向post。将pre指向pre的next指向的节点的next指向的节点。返回dummy的next指向的节点。
具体双指针代码实现如下
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: ListNode) - ListNode:# 定义虚拟节点dummydummy ListNode(0)dummy.next headpre dummywhile pre.next and pre.next.next:cur pre.nextpost cur.nextcur.next post.nextpost.next curpre.next postpre pre.next.nextreturn dummy.next使用虚拟节点递归实现的思路
定义虚拟节点dummy并将其next指向头节点。如果链表不为空则从头节点开始递归每次递归都会交换当前节点与其后面的节点。对于每次递归通过将当前节点的next指向其后面的节点的next指针并递归当前节点的next指针实现链表节点的交换。递归边界为当前节点的next指针为None或只有一个节点时。完成递归后返回头节点即可。
具体递归代码实现如下
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: ListNode) - ListNode:# 定义虚拟节点dummydummy ListNode(0)dummy.next headif head and head.next:next_node head.next.nexthead.next.next headhead.next self.swapPairs(next_node)dummy.next head.nextreturn dummy.next如果使用动态状态方程写的话可以更加简洁
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: ListNode) - ListNode:# 定义虚拟节点dummydummy ListNode(0)dummy.next headif head and head.next:head.next, dummy.next.next, dummy.next self.swapPairs(head.next.next), head, head.nextreturn dummy.nextB站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1YT411g7br/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 5、删除链表的倒数第N个节点 给你一个链表删除链表的倒数第 n **个结点并且返回链表的头结点。 示例1 输入head [1,2,3,4,5], n 2
输出[1,2,3,5]示例2
输入head [1], n 1
输出[]示例3
输入head [1,2], n 1
输出[1]提示
链表中结点的数目为 sz
1 sz 30
0 Node.val 100
1 n sz删除链表的第n个节点跟我们之前练习数组的题目移除元素类似我们可以使用快慢指针的方法来实现它。如果要删除倒数第n个节点我们可以让fast移动n步然后让fast和slow同时移动直到fast指向链表末尾最后删掉slow所指向的节点就可以了。同样的我们继续使用虚拟头节点来解决这个问题。 ✍ 快慢指针法的思路如下 定义虚拟节点dummy把dummy的next指向head并定义快指针fast和慢指针slow都指向dummy。先将快指针移动n1步使其到达链表的结尾或倒数第n个位置。然后同时移动快指针和慢指针直到快指针到达链表的末尾。最后把慢指针的下一个节点删除。返回dummy的next作为新的链表的头结点。
具体代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:dummy ListNode(0)dummy.next headslow dummyfast dummyfor i in range(n 1):fast fast.nextwhile fast:slow slow.nextfast fast.nextslow.next slow.next.nextreturn dummy.next我们还可以换一种写法来实现
首先我们新增一个虚拟节点 dummy它的下一个节点是原链表的头节点 head。然后我们定义两个指针 slow 和 fast它们都从 dummy 出发最开始 fast 指针先往前走 n 步。接着两个指针同时向前走当 fast 指针到达结尾后slow 的下一个节点就是倒数第 N 个节点。最后我们直接删除该节点然后返回 dummy.next 即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:dummy ListNode()dummy.next headslow, fast dummy, dummywhile(n!0): #fast先往前走n步fast fast.nextn - 1while(fast.next!None):slow slow.nextfast fast.next#fast 走到结尾后slow的下一个节点为倒数第N个节点slow.next slow.next.next #删除return dummy.nextB站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1vW4y1U7Gf/?spm_id_from333.788 6、相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SzDLGQGH-1676269812178)(https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)]
题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中从头节点开始跳到交叉节点的节点数
skipB - 在 listB 中从头节点开始跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。
示例1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8
解释相交节点的值为 8 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。
在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。
— 请注意相交节点的值不为 1因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说它们在内存中指向两个不同的位置而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点B 中第四个节点) 在内存中指向相同的位置。示例2 输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1
输出Intersected at 2
解释相交节点的值为 2 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。
在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2
输出null
解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。
由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。
这两个链表不相交因此返回 null 。提示
listA 中节点数目为 m
listB 中节点数目为 n
1 m, n 3 * 104
1 Node.val 105
0 skipA m
0 skipB n
如果 listA 和 listB 没有交点intersectVal 为 0
如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]进阶你能否设计一个时间复杂度 O(m n)、仅用 O(1)内存的解决方案 这道题有A,B两个方向需要遍历所以我们可以让两个指针同时从两个链表的头节点开始走直到两个指针相遇或者其中一个指针遍历完了自己的链表此时再将该指针指向另一个链表的头节点并继续遍历直到两个指针相遇此时相遇的节点即为第一个公共节点。 ✍ 具体实现的思路是 创建两个指针pA和pB分别指向两个链表的头结点headA和headB。 先判断两个链表是否存在交点 a. 如果pA pB则返回pA说明此时两个指针所指向的结点就是交点。 b. 如果pA ! pB则继续遍历 i. 若pA存在则将pA移动到pA.next否则将pA指向headB ii. 若pB存在则将pB移动到pB.next否则将pB指向headA。 循环2的步骤直到pA pB或pA和pB均不存在此时说明两个链表没有交点或已经找到了交点。
知道了具体实现思路那么写出代码也就不是很难了具体代码实现是
# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val xself.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:pA headApB headBwhile pA ! pB:pA pA.next if pA else headBpB pB.next if pB else headAreturn pA我们使用的这种方法的优点在于不论两个链表的长度是否相等最多只需要遍历两次链表时间复杂度为O(m n)其中m和n分别是两个链表的长度。 7、环形链表Ⅱ 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示
链表中节点的数目范围在范围 [0, 104] 内
-105 Node.val 105
pos 的值为 -1 或者链表中的一个有效索引进阶你是否可以使用 O(1)空间解决此题 当我们看到这个题目的时候我们首先要了解题目的意思简单的来说就是给定一个链表判断是否存在环如果存在环则找到环的入口。知道题目的意思之后我们就知道题目的重点在于用什么方法判断是否存在环以及如何找到环的入口我们可以联想到我们之前经常用到的方法那就是快慢指针的方法实现方法大概就是用两个指针fast和slow分别指向head每次将fast移动到fast.next.next将slow移动到slow.next也就是快指针移动的速度是满指针的两倍如果fast slow则说明存在环。解决完判断是否存在环的问题之后我们还要思考如何找到环的入口我们可以将slow指向head同时保持fast不变再次每次将slow移动到slow.next将fast移动到fast.next如果在某一时刻slow fast则说明slow和fast所指向的结点即为环的入口。 ✍ 知道了解决思路之后我们就可以写出代码了。 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: ListNode) - ListNode:fast slow headwhile fast and fast.next:fast fast.next.nextslow slow.nextif fast slow:slow headwhile slow ! fast:slow slow.nextfast fast.nextreturn slowreturn None上述算法的实现步骤为
创建两个指针fast和slow分别指向head。每次将fast移动到fast.next.next将slow移动到slow.next。如果fast slow说明链表存在环。此时将slow指向head同时保持fast不变再次每次将slow移动到slow.next将fast移动到fast.next。如果在某一时刻slow fast则说明slow和fast所指向的结点即为环的入口。如果fast不存在或fast.next不存在则说明链表不存在环返回None。
B站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from333.1007.top_right_bar_window_history.content.clickvd_sourceeae0406d86828f39f6ac3a3b0e8a2a34
