链表
1. 哈希表
- 简单介绍：
（1）哈希表在使用层面上可以理解位一种集合结构
（2）如果只有key，没有伴随数据value，可以使用HashSet结构（C++中叫UnOrderedSet)
（3）如果即有key，又伴随数据value，可以使用HashMap结构（C++中叫UnOrderedMap）
（4）有无伴随数据，是HashMap和HashSet的唯一区别，底层的实际结构是相同的
（5）使用哈希表的增（put），删（remove），查（contains）和改（put）操作，可认为实际复杂度是O(1)，但是常数时间比较大
（6）放入哈希表的东西，如果key(键)是基础数据类型，内部按值传递（哈希表内部拷贝一份相同的key），内存占用就是key这个东西的大小
（7）放入哈希表的东西，如果key(键)不是基础类型（自定义类型），内部按照引用传递（哈希表内部拷贝key的内存地址,8字节），内存占用是key这个东西的内存地址 - 演示：
HashSet： HashSet<Integer> hashSet = new HashSet<>(); //创建对象 hashSet.add(3); //添加3元素 System.out.println(hashSet.contains(3)); //检测元素是否存在 hashSet.remove(3); //删去3 System.out.println(hashSet.contains(3));
HashMap： HashMap<Integer, String> hashMap1 = new HashMap<>(); hashMap1.put(1, "a"); //增加key - value System.out.println(hashMap1.get(1)); System.out.println(hashMap1.containsKey(1)); //检查对应的key是否存在 hashMap1.put(1, "A"); //改key为1 对应的value System.out.println(hashMap1.get(1)); hashMap1.put(2, "b"); hashMap1.remove(2); System.out.println(hashMap1.get(2));
2. 有序表
- 简单介绍
（1）有序表在使用层面上可以理解位一种集合结构
（2）如果只有key，没有伴随数据value，可以使用TreeSet结构（C++中叫OrderedSet）
（3）如果既有key，又有伴随数据value，可以使用TreeMap结构（C++中叫OrderedMap）
（4）有无伴随数据，是TreeSet和TreeMap唯一的区别，底层内容相同
（5）有序表与哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织。所以哈希表有的功能，有序表也有。同时有序表因为key有序同时新增了一些功能：firstKey()：最小的key；lastKet()：最大的key；floorKey(x)：<=x的key中离x最近的……在性能上有序表略差于哈希表。有序表增删查改的时间复杂度为O(logN)级别的
（6）红黑树，AVL树，size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
（7）放入有序表的东西，如果key是基础数据类型，内部按值传递，内存占用就是这个东西的大小
（8）放入有序的东西，如果key不是基础类型，必须提供比较器（key值的比较），内部按照引用传递，内存占用是这个东西的内存地址
（9）不管是什么底层的具体实现，只要是有序表，都有以下固定的基本功能和时间复杂度
- 演示：
TreeMap<Integer, String> treeMap = new TreeMap<>(); treeMap.put(7, "我是7"); treeMap.put(5, "我是5"); treeMap.put(2, "我是2"); treeMap.put(3, "我是3"); treeMap.put(9, "我是9"); treeMap.put(4, "我是4"); System.out.println(treeMap.containsKey(5)); System.out.println(treeMap.get(5)); System.out.println(treeMap.get(6)); System.out.println(treeMap.firstKey()); //最小 System.out.println(treeMap.lastKey()); //最大 System.out.println(treeMap.floorKey(8)); //<=8 System.out.println(treeMap.ceilingKey(8)); //>=8 treeMap.remove(5); System.out.println(treeMap.containsKey(5));
3. 链表
- 概念
题目一：单链表回文数判断
- 笔试思路：使用栈的结构解决问题，先将整个链表压入一个栈中，再将栈中元素出栈与链表依次比较，当出现一个不同，就表示不是回文数，若栈空且满足条件则就是回文数，此方法的时间复杂度是O(N)
优化思路：在存入栈时，只存储右半部分（从中间到尾部依次存入栈），出栈的比较就是左边与右边的比较，只要栈空且满足条件就是回文数，此方法便可将空间复杂度降低到O(N/2)
关键点：如何寻找单链表的中间结点？
解决方法：快慢双指针，快指针一次走两个结点，慢指针一次走一个结点。当快指针到达链表尾部时，慢指针就是中点位置。方法细节：有无头结点；总的结点数是奇数还是偶数（对应中间值不同）；当结点个数较少时的特殊情况……
public static Node doubleNode(Node head){ //存在头结点的情况 if (head.next == null || head == null){ //链表为空 return null; } Node fast = head; Node slow = head; while (fast.next.next != null && slow.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } public static boolean isPalindrome(Node head){ Node p = head.next; Node slow = doubleNode(head); Stack<Node> stack = new Stack<Node>(); //栈的准备 while (slow != null){ //入栈 stack.push(slow); slow = slow.next; } while (!stack.isEmpty()){ //出栈 if (p.value != stack.pop().value){ return false; } p = p.next; } return true; }
- 面试思路：先找到中点后，改变右半部分指针的方向，使其由右向左指。同时从头尾去双指针开始比较，一样就比较下一个直至到中点。此方法的空间复杂度可以达到O(1)
关键点：要将右半部分的指针改2次，第一次使其由右指向左，然后进行比较，比较完后，在恢复为正常链表：由左向右，采用三指针的方法依次改变指针的指向，在移动指针
public static boolean isPalindrome(Node head){ if (head == null || head.next ==null){ //为空与只有一个头结点的判断 return true; } Node fast = head; Node slow = head; while (fast.next.next != null && slow.next != null){ //找中点 fast = fast.next.next; slow = slow.next; } Node right = slow.next; //右半部分的头指针 slow.next = null; //从中r间先断开两部分 Node p, q = slow, r = right; while (r != null){ //第一次改变右部分指针的指向 //最终q指针是最右边的指针 p = r.next; r.next = q; q = r; r = p; } p = head.next; //最左边第一个 r = q;//最右边的 boolean flag = true; //记录是否为回文 while (p != null && q != null){ //双指针同时移动测试是否为回文数 if (p.value != q.value){ flag = false; break; } p = p.next; q = q.next; } q = null; while (r != null){ //第二次恢复右部分指针指向 p = r.next; r.next = q; q = r; r = p; } slow.next = right; //左右相连 return flag; }
题目二：划分单链表
- 笔试思路：创建类型为Node的数组，将整个链表存入数组，再在数组中进行一次partition操作（快速排序的一次划分）
细节点：数组变链表，直接遍历数组中的结点使nodes[i - 1].next = nodes[i]
public static Node listPartition(Node head, int pivot){ if (head == null || head.next == null){ return head; } Node p = head.next; int i = 0; while (p != null){ //统计结点数 i++; p = p.next; } Node[] nodes = new Node[i]; p = head.next; for (i = 0; i < nodes.length; i++){ //将链表存入数组 nodes[i] = p; p = p.next; } partition(nodes, pivot); for (i = 1; i < nodes.length; i++){ //将数组变成链表 nodes[i - 1].next = nodes[i]; } nodes[i - 1].next = null; //尾结点 return nodes[0]; //返回头结点 } public static void partition(Node[] nodes, int pivot){ int small = -1; //小于区 int big = nodes.length; //大于区 int index = 0; //指针目前位置 while (index < big){ if (nodes[index].value < pivot){ swap(nodes, ++small, index++); } else if (nodes[index].value > pivot){ swap(nodes, --big, index); } else { index++; } } } public static void swap(Node[] nodes, int i, int j){ Node temp = nodes[i]; nodes[i] = nodes[j]; nodes[j] = nodes[i]; }
- 面试思路：6个指针，小于区，等于区，大于区的头尾指针，遍历链表将符合关系的结点放入对应的区域，最终将小于区的尾与等于区的头相连，等于区的尾与大于区的头相连即可
细节点：在小于区，等于区或等于区有区域为空时，要特殊处理
方法优点：可以保持稳定性
public static Node listPartition(Node head, int pivot){ Node sH = null; //small head Node sT = null; //small tail Node eH = null; //equal head Node eT = null; //equal tail Node bH = null; //big head Node bT = null; //big tail Node p = head.next; Node q; while (p != null){ //遍历链表 q = p.next; p.next = null; //使结点间关系断开 if (p.value < pivot){ //小于区 if (sH == null){ //先要判断是否为空 sH = p; sT = p; } else { sT.next = p; sT = p; } } else if (p.value == pivot){ //等于区 if (eH == null){ //先要判断是否为空 eH = p; eT = p; } else { eT.next = p; eT = p; } } else{ //大于区 if (bH == null){ //先要判断是否为空 bH = p; bT = p; } else { bT.next = p; bT = p; } } p = q; //移动指针 } if (sH != null){ //存在小于区 sT.next =eH; //小于区的尾连等于区的头 //判断等于区是否存在，不存在直接使小于区的尾变成null eT = eT != null ? eT : sT; } if (eT != null){ //连大于区的头 eT.next = bH; } return sH != null ? sH : (eH != null ? eH : bH); }
题目三：含随机指针结点的链表复制
难点：存在随机指针，如何在老节点的关系基础上建立新结点，并且使新结点间的关系与老结点之间的关系相同
- 笔试思路：利用HashMap的数据结构解决，将其的key，value的类型均设为Node类型，key为老结点，value为新结点，便可轻松解决新老结点的对应关系
public static Node copeNode(Node head){ Node p = head; HashMap<Node, Node> map = new HashMap<Node, Node>(); while (p != null){ //将新，旧结点放入HashMap map.put(p, new Node(p.value)); p = p.next; } p = head; while (p != null){ //将next,rand指针copy给新结点 //map.get(p)得到的是新结点 //map.get(p.next)得到的是与旧结点对应关系的新结点 //map.get(p).next = map.get(p.next)，使新结点间建立关系 map.get(p).next = map.get(p.next); map.get(p).rand = map.get(p.rand); p = p.next; } return map.get(head); }
- 面试思路：不使用哈希表完成，先将新生成的结点之间插入到对应的旧节点之后，便可维持对应关系。首先先调整新生成结点rand的指针，将新旧结点一对一对的进行调整，旧指针的rand指的旧结点，新指针的rand先根据旧的rand找到旧结点，再通过旧结点的next指针找到新结点的rand对应值（例如：old1.read = old3; new1.rand = old1.rand.next; //old3.next = new.3)。最好遍历链表将新旧指针分离即可
public static Node copeNode(Node head){ Node p = head; while (p != null){ //新旧指针合并 //1 -> 2 //1 -> 1' -> 2 -> 2' Node q = new Node(p.value); //新指针 q.next = p.next; p.next = q; p = q.next; //跳过新指针，到下一个旧指针 } p = head; while (p != null){ //新指针rand指针域的建立 p.next.rand = p.rand.next; p = p.next.next; //需要跳过新指针 } p = head; Node copyHead = head.next; //复制的头结点 while (p != null){ //新旧指针的分离 //双指针交换进行 Node q = p.next; p.next = q.next; q.next = p.next; p = p.next; } return copyHead; }
题目四：两链表相交问题（是否有环，是否相交）
- 问题1：如何判断单链表是否有环
笔试思路：哈希表（HashSet）结构解决问题，遍历链表将结点存入Node类型的哈希表，每次存入结点前先判断哈希表中有无对应的结点存在，若有：则说明有环且该结点就是第一个入环结点，若无最终遍历到空结点，则说明无环
public static Node getLoopNode(Node head){ //得到单列表的入环结点 if (head == null || head.next == null){ return null; } HashSet<Node> hashSet = new HashSet<Node>(); Node p = head.next; set.add(p); while (p != null){ //遍历链表 if (set.contains(p.next)){ //有环 return p.next; } p = p.next; set.add(p); //HashSet加中入结点 } return null; //无环 }
面试思路：快慢指针，快指针一次俩步，慢指针一次一步。若快指针指向了空结点则说明无环。若有环，则快指针先入环，慢指针后入环，二者一定在环中相遇且在环中遍历的次数最多不超过环长的俩倍。快慢指针相遇，说明有环，此时慢指针不动，快指针移到头部，将快指针也变成一次一步，俩个指针在同时出发，当二者再次相遇时，对应的结点就是入环结点
public static Node getLoopNode(Node head){ //得到单列表的入环结点 if (head == null || head.next == null){ return null; } Node fast = head.next.next; Node slow = head.next; while (fast != slow){ //判断有无环 if (fast == null || slow == null || fast.next != null){ //fast可以直到空指针说明无环 return null; } fast = fast.next.next; slow = slow.next; } fast = head; //fast回到头指针 while (fast != slow){ //找入环结点 fast = fast.next; //改变快指针 slow = slow.next; } return slow; }
- 问题2：如何判断俩个单链表是否相交
- 若两个单链表均没有环
笔试思路：先将一个链表存入HashSet，在遍历另一个链表同时检查HashSet中有无相同结点，若没有则不相交，若存在则相交。返回相交结点
public static Node noLoop(Node head1, Node head2){ //在无环情况下，判断是否相交 if (head1 == null || head2 == null){ return null; } Node p = head1.next; HashSet<Node> hashSet = new HashSet<Node>(); while (p != null){ //链表一加入set hashSet.add(p); p = p.next; } p = head2.next; while (p != null){ //判断是否相交 if (hashSet.contains(p)){ return p; } p = p.next; } return null; }
面试思路：先分别遍历两个链表，得到对应的尾结点和结点长度。若俩链表相交，其尾部份一定完全相同所以随后判断尾结点是否相同：只有相同才能相交，若不同一定不相交。找第一个相交结点：先使长链表走与短链表的长度差出来，随后二者一起移动并比较结点是否相同
public static Node noLoop(Node head1, Node head2){ //在无环情况下，判断是否相交 if (head1 == null || head2 == null){ return null; } Node end1 = head1; Node end2 = head2; int len1 = 0; int len2 = 0; while (end1.next != null){ //遍历链表一 len1++; end1 = end1.next; } while (end2.next != null){ //遍历链表一 len2++; end2 = end2.next; } if (end1 != end2){ //不相交 return null; } Node p = (len1 - len2) > 0 ? head1 : head2; //p为长链表 Node q = p == head1 ? head2 : head1; //q为短链表 int n = Math.abs(len1 - len2); while (n > 0){ //长链表先将走长度差 p = p.next; n--; } while (p != q){ p = p.next; q = q.next; } return p; }
- 一个有环一个无环相交：不可能出现，因为是单链表，每个结点只有一个next指针
- 两个链表均有环
情况分析：（1）不相交（2）入环结点相同（3）入环结点不同
思路分析：先通过问题1，得到两个结点的入环结点。若两个入环结点相同（2）的情况，则可以看成结尾结点为入环结点的两个无环链表求第一个相交结点的问题。入环结点不同则为情况（1）或者（3），此时遍历其中的一个环，在遍历的过程中检测是否有另一个链表的入环结点存在，若存在则相交，若不存在则不相交
public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2){ //两个链表均有环 Node p; Node q; if (loop1 == loop2){ //入环结点相同，转化成求从head到loop有相交结点的问题 p = head1; q = head2; int len1 = 0; int len2 = 0; while (p != loop1){ //head1 -> loop1 len1++; p = p.next; } while (q != loop2){ //head2 -> loop2 len2++; q = q.next; } p = (len1 - len2) > 0 ? head1 : head2; //p为长链表 q = p == head1 ? head2 : head1; //q为短链表 int n = Math.abs(len1 - len2); while (n > 0){ //长链表先将走长度差 p = p.next; n--; } while (p != q){ p = p.next; q = q.next; } return p; }else { //不相交或入环结点不同 p = loop1.next; while (p != loop1){ //环的遍历 if (p == loop2){ return loop2; } p = p.next; } return null; } }
- 方法调用：
public static Node getIntersectNode(Node head1, Node head2){ //两结点有无相交结点，及求首个相交结点 if (head1 == null || head2 == null){ return null; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); if (loop1 == null || loop2 == null){ //两个无环链表 return noLoop(head1, head2); } else if (loop1 != null && loop2 != null){ return bothLoop(head1, head2, loop1, loop2); } return null; //其余情况不可能相交 }
- 整体代码：
public static Node getIntersectNode(Node head1, Node head2){ //两结点有无相交结点，及求首个相交结点 if (head1 == null || head2 == null){ return null; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); if (loop1 == null || loop2 == null){ //两个无环链表 return noLoop(head1, head2); } else if (loop1 != null && loop2 != null){ return bothLoop(head1, head2, loop1, loop2); } return null; //其余情况不可能相交 } public static Node getLoopNode(Node head){ //得到单列表的入环结点 if (head == null || head.next == null){ return null; } Node fast = head.next.next; Node slow = head.next; while (fast != slow){ //判断有无环 if (fast == null || slow == null || fast.next == null){ return null; } fast = fast.next.next; slow = slow.next; } fast = head; //fast回到头指针 while (fast != slow){ //找入环结点 fast = fast.next; //改变快指针 slow = slow.next; } return slow; } public static Node noLoop(Node head1, Node head2){ //在无环情况下，判断是否相交 if (head1 == null || head2 == null){ return null; } Node end1 = head1; Node end2 = head2; int len1 = 0; int len2 = 0; while (end1.next != null){ //遍历链表一 len1++; end1 = end1.next; } while (end2.next != null){ //遍历链表一 len2++; end2 = end2.next; } if (end1 != end2){ //不相交 return null; } Node p = (len1 - len2) > 0 ? head1 : head2; //p为长链表 Node q = p == head1 ? head2 : head1; //q为短链表 int n = Math.abs(len1 - len2); while (n > 0){ //长链表先将走长度差 p = p.next; n--; } while (p != q){ p = p.next; q = q.next; } return p; } public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2){ //两个链表均有环 Node p; Node q; if (loop1 == loop2){ //入环结点相同，转化成求从head到loop有相交结点的问题 p = head1; q = head2; int len1 = 0; int len2 = 0; while (p != loop1){ //head1 -> loop1 len1++; p = p.next; } while (q != loop2){ //head2 -> loop2 len2++; q = q.next; } p = (len1 - len2) > 0 ? head1 : head2; //p为长链表 q = p == head1 ? head2 : head1; //q为短链表 int n = Math.abs(len1 - len2); while (n > 0){ //长链表先将走长度差 p = p.next; n--; } while (p != q){ p = p.next; q = q.next; } return p; }else { //不相交或入环结点不同 p = loop1.next; while (p != loop1){ //环的遍历 if (p == loop2){ return loop2; } p = p.next; } return null; } }
- 注意点：fast.next.next的时候若此时fast.next已经为空，就会发生报错，（NullPointerException），所以在条件判断是要保证fast.next不为空
