写在前面
面试准备算法篇之一。链表。
Hash算法
链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储,链表在插入的时候可以达到 O(1)O(1) 的复杂度,比另一种线性表 —— 顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n)O(n) 的时间,而顺序表相应的时间复杂度分别是 O(log\ n)O(log n) 和 O(1)O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(links)。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。
链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。
链表通常可以衍生出循环链表,静态链表,双链表等。对于链表使用,需要注意头结点的使用。
经典题目(leetcode)
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
1 | 给定两个数组,编写一个函数来计算它们的交集。 |
解题
1 | /** |
解题思路
遍历链表,从当前节点向后遍历,删除相同val值的元素。达到去重的目的。
奇偶链表
1 | 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 |
解题
1 | /** |
解题思路
首先定义两个链表头, 奇偶链表头。奇偶链表头分别引用链表第一,第二个节点。再以奇偶链表头为基础节点开始遍历。
动态将节点的cur.next.next指针赋给cur.next。同时继续遍历。
当当前节点.next不存在的时候则节点遍历结束。将偶数节点头赋到奇数cur节点。即完成了奇偶节点的分割拼接。

