2. 链表

1. 哈希表简单介绍

1）哈希表在使用层面上可以理解为一种集合结构

2）如果只有key，没有伴随数据value，可以使用HashSet结构

3）如果既有key，又有伴随数据value，可以使用HashMap结构

4）有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事

5）使用哈希表增（put）、删（remove）、改（put）和查（get）的操作，可以认为时间复杂度为O(1)，但是常数时间比较大

6）放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小(key=基础类型大小)

7）放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用就是这个东西内存地址(key一律是8字节)

todo哈希表实现原理

2. 有序表简单介绍

1）有序表在使用层面上可以理解为一种集合结构

2）如果只有key，没有伴随数据value，可以使用TreeSet结构

3）如果既有key，又有伴随数据value，可以使用TreeMap结构

4）有无伴随数据，是TreeSet和TreeMap的唯一的区别，底层的时间结构是一回事

5）有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织

6）红黑树、AVL树、size-balance-tree和跳表等 都属于有序表结构，只是底层具体实现不用

7）放入有序表的东西，如果是基础类型，内部按照值传递，内存占用就是这个东西的大小

8）放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用就是这个东西内存的大小

9）不管是什么底层实现，只要是有序表，都有固定的时间复杂度O(logN)

todo实现原理

3. 反转单向和双向链表

注意换头结点

题目：分别实现反转单向链表和反转双向链表

要求：如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

4. 打印两个链表的公共部分

题目：给定两个有序链表的头指针head1和head2，打印两个链表的公共部分

如果：两个链表的长度之和为N，时间复杂度要求为O(N),额外空间复杂度要求为O(1)

5. 面试时链表解题的方法论

1）对于笔试，不用太在乎空间复杂度，一切为了时间复杂度

2）对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

重要技巧：

1）额外数据结构记录(哈希表等)

2）快慢指针

6. 判断一个单链表是否是回文结构

题目：给定一个单链表的头结点head，请判断该链表是否为回文结构。

例子：1->2->1，返回true；1->2->2->1，返回true；15->6->16。返回true；1->2->3，返回false。

要求：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

# 利用栈，两次遍历链表    时间复杂度达到O(N)，额外空间复杂度(N)
# 利用栈，快慢指针，将后边入栈；两次遍历链表。  时间复杂度达到O(N)，额外空间复杂度O(N/2)
# 边界条件，如果是偶数，慢指针在中间数前、后 123321 第一个3，第二个3
# 边界条件，快指针走完，慢指针在中间数前前一个，后后一个  123321 慢指针第一个2，慢指针后一个2 
    

# 有限变量  时间复杂度达到O(N)，额外空间复杂度(1)
1. 快慢指针，慢指针 指null，后半部分逆序
2. A、B两个头向中间同时遍历
3. 将后半部分逆序处理成正常，中间节点指向正确

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

题目：给定一个单链表的头结点head，节点的值类型是整形，在给定一个整数prvot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点

进阶：在实现原问题功能的基础上增加如下的要求

要求1：调整后所有小于pivot的节点之间的相对顺序和调整前一样

要求2：调整后所有等于pivot的节点之间的相对顺序和调整前一样

要求3：调整后所有大于pivot的节点之间的相对顺序和调整前一样

要求4：时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

# Node类型数组，数组partition

# 6个变量
sh=null 小于区头
st=null 小于区尾
eh=null 等于区头
et=null 等于区尾
bh=null 大于区头
bt=null 大于区尾    

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

题目：一种特殊的单链表解答类描述如下

class Node{
    int value;
    Node next;
    Node rand;
    Node(int val){
        value = val;
    }
}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

要求：时间复杂度O(N)，额外空间复杂度O(1)

# 哈希表
Map<老节点，新节点> map
设置next和rand设置
遍历老链表，map.get(老节点)
    
public static Node copyListWithRand(Node head){
    Map<Node,Node> map = new HashMap<>();
    Node cur = head;
    while(cur!=null){
        map.put(cur,new Node(cur.value));
    }
    cur = head;
    while(cur!=null){
        map.get(cur).next = map.get(cur.next);
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}    

# 链表挂节点，3个while循环
将复制节点挂在原先节点下 
成对拿到节点，一对对设置rand节点
在next方向上将next节点断开    

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

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

要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

# 判断链表是否又环
快指针走两步，慢指针走一步
等快指针和慢指针在环上某一个位置相遇
快指针回到头节点，慢指针不动
快指针走一步，慢指针走一步。下次相遇就是第一个入环节点
    
head1                          head2
loop1(head第一个相交节点)        loop2(head2第一个相交节点) 
1）loop1=null && loop2=null
head1和head2都无环
遍历head1的节点，最后一个节点end1，长度len1    
遍历head2的节点，最后一个节点end2，长度len2  
判断end1是否等于end2
    如果end1<>end2,表示两个链表不相交
    如果end1=end2,表示两个链表相交，|len1-len2|长度长的先走长度差步数，两个节点依次走一步，两个节点会在第一个相交节点相遇
2）（loop1!=null && loop2=null）|| （loop1=null && loop2！=null）
head1和head2不同时为空，表示没有相交节点
3）loop1!=null && loop2!=null
3.1) 两个环不想交
    loop1接着每次走一步，转到loop1之前没有遇到loop2
3.2) 两个环相交环外
    loop1=loop2，无环链表相交问题
3.3) 两个环相交环内
    loop1接着每次走一步，转到loop1之前遇到loop2。返回loop1或loop2都对