链表python,链表c语言

http://www.itjxue.com  2023-01-22 03:35  来源:未知  点击次数: 

python定义链表数据结构

4

开始遍历此链表

15

14

13

12

链表遍历已经结束

None

开始遍历此链表

15

14

111

13

12

链表遍历已经结束

None

开始遍历此链表

111

15

14

111

13

12

链表遍历已经结束

None

开始遍历此链表

111

111

15

14

111

13

12

链表遍历已经结束

None

python中链式存储有哪些

顺序存储结构最大的缺点是插入和删除时需要移动大量元素,耗费大量时间。

如果让相邻元素间留有足够余地,也就是不考虑相邻位置了,那么,我们这里可以引入链式存储结构。

链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

二、链表的定义

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。

1、单向链表

单向链表也叫单链表,是链表中最简单的一种形式,一个信息域(元素域)和一个链接域组成一个节点。

这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

链表的每个结点中只包含一个链接域,所以叫做单链表。

表元素域elem用来存放具体的数据。

链接域next用来存放下一个节点的位置(python中的标识)

变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

链表中第一个结点的长处位置叫做头指针

显著性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)

通常会在单链表的第一个结点前附设一个结点,称为头结点。它的信息域可以不存储数据,也可以存储线性表长度等附加信息,头结点的链接域指向第一个结点的指针。

头指针与头结点的异同

无论链表是否为空,头指针均不为空,头指针是链表的必要元素;头结点不一定是链表的必要要素。

头指针具有标识作用,所以常用头指针冠以链表的名字。

160. 相交链表(Python)

难度:★★☆☆☆

类型:链表

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出:Reference of the node with value = 8

输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出:Reference of the node with value = 2

输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,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。

注意:

如果两个链表没有交点,返回 null.

在返回结果后,两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

这道题与 【题目141. 环形链表】 属于同一题型,环形链表可以使用快慢指针判断,这里我们同样使用双指针进行判别,不过步长都是一步,让两个指针分别从两个链表头结点开始向后移动,当其中一个指针走到链表末尾后,换到另一个链表的头结点上,另一个指针也是如此,这样如果两个链表相交,则一定可以相遇,且根据数量关系可知,首次相遇的结点即为相交结点。

如有疑问或建议,欢迎评论区留言~

(责任编辑:IT教学网)

更多

推荐PHP+MySQL视频文章