每日一句：二十岁的年纪，为什么不敢去折腾？哪怕最后失败，你也还有从头再来的资本。

正如乔布斯所说：你本就一无所有，没有理由不去追随你的内心。

目录

哈希表的简单介绍

有序表的简单介绍

有序表的固定操作

判断一个链表是否为回文结构

 将单向链表按某值划分成左边小，中间相等，右边大的形式

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

两个单链表相交的一系列问题

一个链表怎么判断有无环，若有环，返回第一个入环节点

---

哈希表的简单介绍

1. 哈希表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随数据value，可以使用HashSet结构
3. 如果既有key，又有伴随数据value，可以使用HashMap结构
4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
5. 使用哈希表增put，删remove，改put和查get的操作，可以认为时间复杂度为O（1），但常数时间比较长
6. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

有序表的简单介绍

1. 有序表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随结构value，可以使用TreeSet结构
3. 如果既有key，又有伴随结构value，可以使用TreeMap结构
4. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
5. 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
6. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
7. 放入有序表的东西，如果是基础类型，内部值传递，内存占用就是这个东西大小
8. 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

有序表的固定操作

1. void put(K key,V value);将一个（key,value）记录加入到表中或者将key的记录更新成value
2. V get(K key);根据给定的key查询value并返回
3. Void remove(K key) 移除key的记录
4. Boolean containskey(K key)询问是否有关于key的记录
5. K firstKey() 返回所有键值的排序结果中最左（小）的那个
6. K lastKey() 返回所有键值的排序结果中最右（大）的那个
7. K floorkey(K key) 如果表中存入过Key，返回Key；否则返回所有键值的排序结果中Key的前一个
8. K ceilingkey(K key) 如果表中存入过Key，返回Key；否则返回所有键值的排序结果中Key的后一个
9. 以上所有操作时间复杂度都是O（），N为有序表含有的记录数

单链表的节点结构

Class Node<V>

{ V value;

 Node next;

}由以上结构的节点依次连接起来所形成的链叫单链表结构

双链表的节点结构

Class Node<V>

{ V value;

 Node next;

 Node last;

}由以上结构的节点依次连接起来所形成的链叫双链表结构

单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有节点

面试时链表解题的方法论

1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
2. 对于面试，时间复杂度依然放在第一位，但一定要找到空间最省的方法

重要技巧：

1. 额外数据结构记录（哈希表等）
2. 快慢指针

判断一个链表是否为回文结构

给定一个单链表的头节点head，请判断该链表是否为回文结构1—>2—>1,返回true；1—>2—>2—>1,返回true；1—>2—>3,返回false；如果链表长度为N，时间复杂度O(N),额外空间复杂度O（1）

笔试：

方法一：1—>2—>3—>3—>2—>1，依次放到栈里，从栈里弹出的顺序与原链表逆序的顺序对比

方法二：用N2方法，找快慢指针；左边开始遍历，每遍历一个，栈弹出一个对比

怎么只把右部分放入栈里去？

快慢指针  快指针每次走2步，慢指针每次走1步

快指针走完时，慢指针来到中间位置，这时把慢指针后边放入栈里去

 

面试：

快指针每次走2步，慢指针每次走1步

快指针走完时，慢指针来到中间位置

1—>2—>3<—2<—1

A—>         <—B

如果A，B每步都一样则回文

 将单向链表按某值划分成左边小，中间相等，右边大的形式

【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot.实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点

【进阶】在实现原问题功能的基础上增加如下要求：调整后所有小于/等于/大于pivot的节点之间的相对顺序和调整前一样

时间复杂度O（N）;额外空间复杂度O（1）（用有限几个变量）

笔试：

把单链表每个节点放到数组里，在数组上partition,在数组里把每个node串起来

面试：

代码：

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

一种特殊的单链表节点类描述如下：

Class Node{

int  value;

Node  next;

Node  rand;

Node(int val)

{ value=val;}

}rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。时间复杂度O（N）,额外空间复杂度O（1）

方法一：

代码：

第一步不用考虑指针怎么连，把老链表都拷贝新链表放到map里去

第二步设置新链表的rand，next方向指针，遍历哈希表或老链表

方法二：

 不用哈希表，利用克隆节点对应的位置关系对应

生成克隆节点，但把克隆节点放在老链表下一个，最后在next方向上把新老指针分离出来

代码：

两个单链表相交的一系列问题

【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2，请实现一个函数，如果两个链表相交，请返回相交的第一个节点，如果不相交，返回null

【要求：】如果两个链表长度之和为N,时间复杂度O（N）,额外空间复杂度O（1）

一个链表怎么判断有无环，若有环，返回第一个入环节点

如果链表上有环，快F，慢S指针一定相遇，相遇后，快指针回到开头，慢指针在原地；之后快慢指针都只走一步，它俩一定在第一个入环节点处相遇

1. 两个链表都无环

遍历第一个链表，一直遍历到最后一个节点，即为end1，长度len1

遍历第二个链表，一直遍历到最后一个节点，即为end2，长度len2

判断end1和end2内存地址是不是一个

若不是一个head1和head2不可能相交

若是一个，找到相交部分第一个节点

1. 一个有环，另一个没有环——不可能相交
2. 两个链表都有环

 

情况讨论：

 

两个无环链表相交问题：

 

 

两个有环链表相交问题：