线性表:
线性表是最简单,最基本,最常用的数据结构。线性表中的数据元素之间存在一对一的关系。即:除了第一个元素,其他元素前面有且只有一个元素;除了最后一个元素,其他元素后面有且只有一个元素。生活中的例子:糖葫芦。
(图片来自网络,侵删)
分类:
根据数据存储结构的不同,大体上可以分为:顺序表,链式表。
顺序表:
在内存中用一块地址连续的空间存放线性表的数据元素,因此查找元素时非常方便。增加或删除元素时,需要移动剩下的元素。
链式表:
不强求用连续的内存空间存放线性表的数据元素。除了基本的数据元素,还有一个标识用于保存逻辑上相邻元素的地址信息。增加或删除元素时,不需要移动元素。
如图所示,(node1-next)是头节点,(node4-next)是尾节点。node1的next指向node2,node2的next指向node3,node3的next指向node4。
LeetCode 练习:
LeetCode 是一个在线的刷题网站,建议上英文网站 https://leetcode.com/ 点击 Problems,在右侧的 Topics 下选择 Linked List。这一步是依据 Topic 选择相应的题目,Linked List 代表了链表。下面我们做几道 Easy 类型的题目巩固一下基础。给出的示例代码不一定是最优解,请做完后阅读Discuss,参考别人的答案。
题目:876.Middle of the Linked List
描述:给定一个非空线性表,返回中间的节点开始的列表。如果中间节点有两个,返回第二个节点后开始的列表。
例如:给定 [1,2,3,4,5],返回 [3,4,5];给定 [1,2,3,4,5,6],返回 [4,5,6]
说明:第一次做题请选择对应的语言。如下图所示,选择了 C#:
思考:
根据示例代码,目的是返回中间的节点。提供的ListNode结构,只有值val与下一个节点next,没有位置标识。
因此我们可以创建一个List集合,遍历head,放入List,然后直接返回中间的节点。参考代码如下:
一般代码写完后,点击下面的 Run Code,初步检查没错后再点击 Submit
代码的运行结果如下:
可见运行速度还是可以的,只是使用的内存稍高一些。
题目:206. Reverse Linked List
描述:链表反转。
思路:相邻对象交换。参考代码如下: