链表

coding问题：

即不涉及算法，仅需知道数据结构怎么使用即可解出的问题

哈希表：

在c++中哈希表为：unordered_map<T,T>

在进行增删改查其时间复杂度为常数级别（但常数级比数组的直接寻址大）

7）补充：内存占用为8字节，与存入数据的内存大小无关

有序表：

进行增删改查时时间复杂度为O(logN)

7）补充：内存占用为8字节，与存入数据的内存大小无关

链表：

单链表：使用struct实现，包含数据和指向下一个节点的指针，类型为自己创建的节点类型

双链表：使用struct实现，包含数据和指向下一个节点和指向上一个节点的指针，类型为自己创建的节点类型

对链表操作的函数，若改变头部有返回值，不改变头部就是用void

两个链表，从头开始比较数据大小，谁小，谁向后移动，相同时候打印并且共同向后移动

将链表的右边部分存入栈中，存完之后将栈中的数依次弹出与原链表左半边做比较（使用快慢指针，快指针走两步，慢指针走一步，当快指针走到底，慢指针刚好到链表中间）此方法用于笔试

使用快慢指针找到链表中点，将链表的后半反转，中间点置空从链表两边开始比较，最后要把右半边链表反转回来（此方法用于面试被提问到时，时间复杂度为O(N)，空间复杂度为O(1)）

将单项链表按某值划分：

笔试：

创建一个node节点类型的数组，将链表中的每个节点存放在数组中，对数组进行partition，之后将数组中的node节点连起来

面试：

准备6个指针分别要指向小于链表，等于链表和大于链表的头和尾，便利链表，比较后连向对应的链表尾部，最后小于连表的尾部连上等于链表的头部，等于链表的尾部连向大于链表的头部（时间复杂度为O(N)，空间复杂度为O(1)）

复制含有随机指针节点的链表

开辟额外空间：

创建一个哈希表，将旧链表存到key种，将新链表存到value中，从表中依次读出并存入新链表

不使用哈希表：

将新链表的内个节点连到旧链表的对应节点的next上每次遍历两个节点

代码:

判断链表种是否存在环结构：

使用额外空间：

创建一个哈希表（set），遍历链表，判断在哈希表中是否存在，不存在，将该节点存入，存在就结束并返回该节点

不使用额外空间：

使用快慢指针，指针若快指针指到空，则链表没有环，若两指针相遇，则链表有环，此时将快指针一会头结点，两指针每次走一个节点再次相遇是所指向的节点变为链表入环的节点

单链表相交:

两个链表先判断是否有环

情况一：若两个链表都没有环

遍历两个链表记录最后一个节点和各自长度，判断两个尾节点地址是否想等，不想等则两链表不想交，不想等时，让长链表先走两链表的长度差值的步数，之后两链表一起走，两指针相等时便为两链表的想交的第一个点

情况二：一个链表有环，一个链表无环，此情况下两链表不会相交

情况三：两个链表都有环

此情况下会再分为三种情况

情况一：

两个链表的入环节点一样，求相交的第一个节点的方法和求两个无环链表的相交节点方法一样。

情况二：

两个链表的入环节点不一样，此时让链表一的入环节点的指针loop1往后走，若再次走到入环节点是未遇到loop2则两链表不想交，若遇到则为另一种情况，loop1，loop2都为两个链表相交的第一个点

以上时间复杂度均为O(N)