Summary
- 哈希表 Hash table
- 有序表 Treeset
- 链表 Linked list
3.1 单链表结构 Single Linked list
3.2 双链表结构 Doubly linked list
3.3 例1：反转单链表和反转双链表 -- leetcode 206 Reverse Linked List (easy)
3.4 例2：打印两个有序链表的公共部分
3.5 链表方法论--笔试和面试要求不同
3.6 例3 ：判断链表是否为回文结构 -- leetcode 234 Palindrome Linked List (easy)
3.7 例4: 将单链表按值划分为左边小，中间相等，右边大的形式 -- leetcode--86 Partition List medium (medium)
3.8 例5：复制含有随机指针节点的链表--leetcode 138 Copy List with Random Pointer (medium)
3.9 例6：两个单链表相交的一系列问题(最难!)3.9.1 HashSet 判断是否有环 -- leetcode 141 Linked List Cycle (easy)
3.9.2 快慢指针判断是否有环 -- leetcode 142 Linked List Cycle II (medium)
3.9.3 两个链表都没环，找到相交的第一个节点
3.9.4 两个链表一个有环，另一个没环 --> 一定不可能相交
3.9.5 两个链表都有环
3.9.6 main函数调用方法
给两个可能有环也可能没环的单链表，头节点head1和head2。如果两个链表相交，返回相交的第一个节点，如果不相交，返回null --> 空间O(1)
1. 哈希表 Hash table
- 哈希表在使用层面上可以理解为一种集合结构
- 有无value是HashMap和HashSet唯一的区别，底层结构相同
- 哈希表增
hashset.add()删hashset.remove()改hashset.put(key,value)查hashset.contains()/hashset.get(key)时间复杂度都是常数级别O(1) - 放入哈希表的东西，如果是基础类型，内部按值传递(拷贝一份放在哈希表)，内存占用就是这个东西的大小
- 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是内存地址，全部8字节
2. 有序表 Treeset
哈希表在使用层面上可以理解为一种集合结构
有无value是TreeMap和TreeSet唯一的区别，底层结构相同
-
有序表跟哈希表的区别是，有序表的key按照顺序组织起来，哈希表没有顺序。所以有序表能提供更多操作：
-
TreeMap.firstKey()最小 -
TreeMap.lastKey()最大 -
TreeMap.floorKey(8)在表中所有<=8 的数中，离8最近的 -
TreeMap.ceilingKey(8)在表中所有>=8 的数中，离8最近的
-
红黑树，AVL树，size-balance-tree都是有序表结构
有序表增
treeset.add()删treeset.remove()改treeset.put(key,value)查treeset.contains()/treeset.get(key)时间复杂度都是O(log N)放入有序表的东西，如果是基础类型，内部按值传递(拷贝一份放在哈希表)，内存占用就是这个东西的大小
放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是内存地址，全部8字节
3.链表 Linked list
- 单链表结构 Single Linked list
Class Node<V>{
V value;
Node next;
}
- 双链表结构 Doubly linked list
Class Node<V>{
V value;
Node next;
Node last;
}
单链表和双链表结构，只需要给一个头节点head，就能找到剩下所有的节点
- 例1：反转单链表和反转双链表 -- leetcode 206 Reverse Linked List (easy)
换头时要返回Node f(head)，换头操作head = f(head)
时间复杂度O(N), 空间复杂度O(1)
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
private ListNode reverse(ListNode prev, ListNode cur) {
if (cur == null) {
return prev;
}
ListNode temp = null;
temp = cur.next;// 先保存下一个节点
cur.next = prev;// 反转
// 更新prev、cur位置
// prev = cur;
// cur = temp;
return reverse(cur, temp);
}
}
- 例2：打印两个有序链表的公共部分
思路：每个链表都有一个指针，谁的数小谁移动，值一样就打印，然后一起移动，直到一个链表越界
public void printCommonPart(Node head1, Node head2){
System.out.print('Common Part:');
while (head != null && head2 != null){
if(head1.value < head2.value){
head1 = head1.next;
}else if (head1.value > head2.value){
head2 = head2.next
}else {
System.out.print(head1.value + " ");
head1 = head1.next;
head2 = head2.next;
}
}
System.out.println();
}
- 链表方法论：
- 笔试：只在乎时间复杂度，不在乎空间复杂度
- 面试：时间复杂度最优，且找到空间最省的方法
- 重要技巧：
- 额外数据结构记录(哈希表等)
- 快慢指针
- 例3 ：判断链表是否为回文结构 -- leetcode 234 Palindrome Linked List (easy)
笔试思路：放进栈里，每出来一个和原链表比较是否相同，有一个不一样就不是
public static boolean isPalindrome(Node head){// need n extra space
Stack<Node> stack = new Stack<Node>();
Node cur = head;
while(cur != null){
stack.push(cur);
cur = cur.next;
}
while(head != null){
if(head.value != stack.pop().value){
return false;
}
head = head.next;
}
return true;
}
优化：使用快慢指针，快指针每次走两步，慢指针每次走一步，快指针遍历完成时，慢指针到中点。此时把后半部分放入栈中，与原链表比对。省一半的空间
注：快慢指针有时需要定制，要coding熟悉
面试优化：时间复杂O(N),空间复杂O(1): 使用快慢指针，快指针每次走两步，慢指针每次走一步快指针遍历完成时，慢指针到中点。后半部分遍历时，逆序后半部分链表(中点指向null)。然后从链表的头尾同时向中间走（使用引用记住头和尾），比较值是否相同，走到空，停止。返回T/F，之前把链表还原成最初的样子
- 例4: 将单链表按值划分为左边小，中间相等，右边大的形式
笔试思路：ArratList<Node>[]在数组中partition
面试思路：时间复杂度O(N)，空间复杂度O(1)
用6个额外变量：LowHead, LowTail, EqualHead, EqualTail, HighHead, HighTail 然后用指针指
public ListNode partition(ListNode head, int x) {
ListNode sH = null;//samll head
ListNode sT = null;//samll tail
ListNode eH = null;//equal head
ListNode eT = null;//equal head
ListNode lH = null;//large head
ListNode lT = null;//large tail
ListNode next = null;//save next node
while (head != null){
next = head.next;
head.next = null;
if(head.val < x){
if(sH == null){
sH = head;
sT = head;
}else{
sT.next = head;
sT = head;
}
}else if(head.val == x){
if(eH == null){
eH = head;
eT = head;
}else{
eT.next = head;
eT = head;
}
}else{
if(lH == null){
lH = head;
lT = head;
}else{
lT.next = head;
lT = head;
}
}
head = next;
}
//small and equal reconnect
if (sT != null){//有小于区域
sT.next = eH;
eT = eT == null? sT : eT;//下一步谁去练大区域的头，谁就变eT
}
//上面的if，不管跑了没有，et
//all reconnect
if(eT != null){
eT.next = lH;
}
return sH != null ? sH :(eH !=null ? eH : lH);
}
leetcode--86 Partition List medium (medium)
不需要等于部分，只需要小于和大于等于
- 例5：复制含有随机指针节点的链表--leetcode 138 Copy List with Random Pointer (medium)
一种特殊的链表节点类描述如下:
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
next指针和正常单链表中next指针的意义 一 样，都指向下一个节点。
rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。
给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个 函数完成 这个链表中所有结构的复制，并返回复制的新链表的头节点。
- 笔试思路：hashmap
key（Node 老节点）value（Node 复制出的新结果）
1‘ next指针，通过查询2的map出来的2’，1‘指向2’。1‘的rand指针，通过查询原链表中1的rand指针指向的节点，map到复制链表的节点，1’rand指向该复制节点。
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<Node,Node>();
Node cur = head;
while(cur != null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null){
//cur 老链表
//map.get（cur）新链表
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
- 面试要求：要求时间复杂度O(N)，空间复杂O(1)
思路：不使用hashmap。- 把复制出来的节点，插入原链表。原链表变成1->1'->2->2'->3->3'，每一个节点指向复制出的节点。
- 找rand节点时，复制出的节点rand指向原节点rand指向的下一个，因为原节点rand指向的下一个，就是复制出来的节点
- output时，通过next.next 删除原链表只留下复制出来的链表
class Solution{
public Node copyRandomList(Node head) {
if (head == null){
return null;
}
Node cur = head;
Node next = null;
//copy node and link to every node
//1 ->2
//1-> 1' ->2
while(cur != null){
next = cur.next;
cur.next = new Node(cur.val);//1->1'
cur.next.next = next;//1->1'->2
cur = next;//
}
cur = head;
Node curCopy = null;
//set copy node random
//1-> 1' ->2->2'
while(cur != null){
next = cur.next.next;
curCopy = cur.next;
curCopy.random = cur.random != null ? cur.random.next : null;
//cur.rand.next是copynode的rand
cur = next;
}
Node res = head.next;
cur = head;
//split
while (cur != null){
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
}
- 例6：两个单链表相交的一系列问题：
给两个可能有环也可能没环的单链表，头节点head1和head2。如果两个链表相交，返回相交的第一个节点，如果不相交，返回null --> 空间O(1)
- 9.1 HashSet 判断是否有环 -- leetcode 141 Linked List Cycle (easy)
时间O(N),空间O(N)
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head != null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
- 9.2 快慢指针判断是否有环 -- leetcode 142 Linked List Cycle II (medium)
时间O(N),空间O(1)
思路：快慢指针，慢指针一次走一步，快指针一次走两步。若有环，两个指针一定相遇。相遇时，快指针回到开头，慢指针不动，两个指针此时都变成一次走一步，再次相遇时，一定在入环节点。
public ListNode getLoopNode(ListNode head){
if(head == null || head.next == null || head.next.next == null){
return null;
}
ListNode slow = head.next;
ListNode fast = head.next.next;//两个点的初始条件不能相同，因为下面while的判断条件时相不相同
while (fast != slow){
if(fast.next == null || fast.next.next == null){
return null;
}
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
- 9.3 两个链表都没环，找到相交的第一个节点
若两个链表都没环，如果相交，那么相交部分一直到最后肯定相同。遍历完两个链表，并记录下长度，对比最后一个节点是否相同。不相同没相交，相同就相交。得知相交后，重新遍历两个链表。方法为，长度长的从长度短的地方开始遍历(例，一个长100，一个长80，重新走的时候，100先走20，然后和80一起走)，两个链表一起走，直到相交节点。
public static Node noLoop(Node head1, Node head2){
if (head1 == null || head2 == null){
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n =0;
while (cur1 != null){
n++;
cur1 = cur1.next;
}
while (cur2 != null){
n--;
cur2 = cur2.next;
}
if(cur1 != cur2){
return null;
}
//n是链表1长度-链表2长度
cur1 = n > 0 ? head1 : head2;//把长的变成cur1
cur2 = cur1 == head1 ? head2 : head1;//把短的变成cur2
n = Math.abs(n);
while(n != 0){
n--;
cur1= cur1.next;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
- 9.4 两个链表一个有环，另一个没环 --> 一定不可能相交
- 9.5 两个链表都有环
- 不相交
- 先相交再入环：
- 分别入环
情况2: 先相交再入环，可以把入环节点作为结束点，跟无loop时的遍历一样，找到入环节点。跟有没有环没关系
情况1和情况3: 把loop1再走一遍，如果能遇到loop2，就是分别入环，遇不到就是不相交。
两链表都有环的情况
public static Node bothLoop(Node head1, Node loop1, Noode head2, Node loop2){
Node cur1 = head1;
Node cur2 = hdea2;
if(loop1 == loop2){//情况2:公用一个loop
cur1 = head1;
cur2 = head2;
int = 0;
while (cur1 != loop1){
n++;
cur1 = cur1.next;
}
while (cur2 != loop2){
n--;
cur2 = cur2.next;
}
//n是链表1长度-链表2长度
cur1 = n > 0 ? head1 : head2;//把长的变成cur1
cur2 = cur1 == head1 ? head2 : head1;//把短的变成cur2
n = Math.abs(n);
while(n != 0){
n--;
cur1= cur1.next;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
}else{//没有公用loop
cur1 = loop1.next;
while(cur1 != loop1){
if(cur1 == cur2){
return cur1;//情况3
}
cur1 = cur1.next;
}
return null;//情况1
}
}
9.6 main函数调用方法
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);
}
if(loop1 != null && loop2 != null){
return bothLoop(head1, loop1, head2, loop2)
}
return null;
}
