数据结构——链表

2018-02-07

链表

什么是链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表的分类：

按照连接方向分类
- 单链表
- 双链表
按照有环和无环
- 普通链表
- 循环链表

特点

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

操作

init():初始化
insert(): 插入
trave(): 遍历
delete(): 删除
find(): 查找

Python实现

class link:
    def __init__(self,val):
        self.elem=val
        self.next=None

常见操作

给定一个整数num，如何在节点值有序的环形链表中插入一个节点值为num的节点，并且保证这个环形单链表依然有序。
给定一个链表中的节点node，但是不给定整个链表的头结点。如何在链表中删除node。要求时间复杂度为O(1)。
给定一个链表的头节点head，在给定一个数num，把链表调整成节点值小于num的节点都在链表的左边，等于num的放在中间，大于num放在右边。
给定两个有序链表头结点head1和head2，打印公共部分。
给定一个单链表的头节点head，实现一个吊证单链表的函数，使得每k个节点之间逆序，如果最后不够k个节点一组，则不调整最后几个节点。
给定单链表的头节点head，链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。
判断链表是否是回文的。
一个链表结构中，每个节点不仅含有一条指向下一个节点的next指针，同时含有一条rand指针，指向任意一个节点。复制这种含有rand指针节点的链表。
判断单链表是否有环。有环返回进入的第一个节点。无环返回空。保证时间复杂度为O(N)，空间复杂度为O(1)。
判断无环单链表是否相交。相交返回第一个相交节点，否则返回空。保证时间复杂度为O(N+M)，空间复杂度为O(1)。
判断有环单链表是否相交。相交返回第一个相交节点，否则返回空。保证时间复杂度为O(N+M)，空间复杂度为O(1)。
给定两个单链表头节点head1和head2，判断两个链表是否相交。相交返回第一个相交节点。否则返回空。