链表

简单介绍

哈希表

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

有序表

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

固定操作

TreeMap<Integer, String> treeMap1 = new TreeMap<>();
treeMap1.put(7, "我是7");
treeMap1.put(5, "我是5");
treeMap1.put(4, "我是4");
treeMap1.put(3, "我是3");
treeMap1.put(9, "我是9");
treeMap1.put(2, "我是2");
System.out.println(treeMap1.containsKey(5));
System.out.println(treeMap1.get(5));
System.out.println(treeMap1.firstKey() + ", 我最小");
System.out.println(treeMap1.lastKey() + ", 我最大");
System.out.println(treeMap1.floorKey(8) + ", 在表中所有<=8的数中，我离8最近");
System.out.println(treeMap1.ceilingKey(8) + ", 在表中所有>=8的数中，我离8最近");
System.out.println(treeMap1.floorKey(7) + ", 在表中所有<=7的数中，我离7最近");
System.out.println(treeMap1.ceilingKey(7) + ", 在表中所有>=7的数中，我离7最近");
treeMap1.remove(5);
System.out.println(treeMap1.get(5) + ", 删了就没有了哦");

单链表、双链表

单链表的节点结构

Class Node<V> {V value;Node next;
}

双链表的节点结构

Class Node<V>{V value;Node next;Node last;
}

反转链表

逆序

注意是否要加返回值

如果有换头操作就要有返回值，如果没有的话可以定义成void类型。

打印两个有序链表的公共部分

谁小，谁移动，相等打印，共同移动，直到超出。

面试时链表解题的方法论

• 笔试时，一切为了时间复杂度，不用太在乎空间复杂度
• 面试时，要尽量找到空间最省的方法

技巧：

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

2）快慢指针

例题

题1

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

时间复杂度O(N), 额外空间复杂度O(1)

• 方法1

把它放入栈中，弹出的和原来的进行一个比较。如果每一步都一样说明是回文。否则不是回文

• 方法2

只把右边的东西放到栈中，比对知道栈里东西全部弹出，如果一样说明是回文。可以节省空间

（快慢指针）这个要写熟

• 方法3

不适用别的数据结构。

使用两个指针，从两个方向向中心移动，比对到中心。

题2

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

• 方法1

放到数组中，进行partition，然后再串成链表

• 方法2

定义6个变量

小于区域的头和尾 SH ST

等于区域的头和尾 EH ET

大于区域的头和尾 BH BT

一定要讨论边界，因为有可能没有某一区域的值

public static Node listPartition2(Node head, int pivot) {Node sH = null; // small headNode sT = null; // small tailNode eH = null; // equal headNode eT = null; // equal tailNode bH = null; // big headNode bT = null; // big tailNode next = null; // save next node// every node distributed to three listswhile (head != null) {next = head.next;head.next = null;if (head.value < pivot) {if (sH == null) {sH = head;sT = head;} else {sT.next = head;sT = head;}} else if (head.value == pivot) {if (eH == null) {eH = head;eT = head;} else {eT.next = head;eT = head;}} else {if (bH == null) {bH = head;bT = head;} else {bT.next = head;bT = head;}}head = next;}// small and equal reconnectif (sT != null) {  //如果有小于区域sT.next = eH;eT = eT == null ? sT : eT; //下一步，谁去连大于区域的头，谁就变成eT}//上面的if，不管是否运行，eT// all reconnectif (eT != null) {  //如果小于区域和等与区域不是都没有eT.next = bH;}return sH != null ? sH : eH != null ? eH : bH;
}

题3

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

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

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

• 方法1

哈希表 map

key -> Node类型 老节点， value -> Node类型 新节点

通过Map查出节点指向的节点，然后给复制出来的每个节点设置指针指向的节点。

• 方法2

不用哈希表的做法

1）生成克隆节点 就挂在老节点的下一个

2）那么新节点的rand指向就是老节点指向的next

3）在next上，把克隆节点拿出来

题4

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

单链表的每一个节点只有一个next，所以成环后不可能再出环。也就是说环上只有一个链

• 怎么找第一个入环节点 (先判断链表有没有环)

1. （设置一个哈希表）

每走一步将链表中的值放入哈希表中，当遇到第一个地址相同的节点，这个节点就是第一入环节点

2. （快慢指针法）

设置两个指针，一个每次走一个节点（慢指针），一次每次走两个节点（快指针），当相遇的时候，快指针回到开头第一个节点并且变成一步指针，然后再一次两指针相遇的节点就是第一入环节点。

public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node n1 = head.next; // n1 -> slowNode n2 = head.next.next; // n2 -> fastwhile (n1 != n2) {if (n2.next == null || n2.next.next == null) {return null;}n2 = n2.next.next;n1 = n1.next;}n2 = head; // n2 -> walk again from headwhile (n1 != n2) {n1 = n1.next;n2 = n2.next;}return n1;
}

• 无环情况

单链表每个节点只有一个next，所以一旦有相交，那么接下来的部分一定都共有。

遍历第一个链表，知道最后一个节点，计为end1，长度length1

遍历第二个链表，最后一个计为end2，长度length2

先判断end1和end2内存是否相等，如果不相等，那么就一定没有相交。

那么长链表先走差值步，然后两链表一起走，相遇节点就是第一个相交节点。

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.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}//n为链表1长度减去链表2长度cur1 = n > 0 ? head1 : head2;   //谁长，谁的头变成cur1cur2 = cur1 == head1 ? head2 : head1;  //短的给cur2n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;  //长的先走差值步}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}            //一起走，相遇就是相交节点return cur1;
}

不可能存在一个有环，一个无环，但是还相交的情况

• 都有环的情况

1. 各自有环，都不相交

有环，并且入环节点地址不一样，那么loop1继续走一次，如果没有遇到了loop2说明是没有相交的。那么久返回null

2. 入环节点是同一个

有环，并且发现end地址相等。那么把第一个入环节点当成end，然后采用无环的方法，就可以找到第一个相交节点。

3. 入环节点不是一个

有环，并且入环节点地址不一样，那么loop1继续走一次，如果遇到了loop2说明是相交的。

这个时候返回loop1或者loop2的入环节点，都可以，都是相交的第一个节点

public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;}cur1 = cur1.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);}if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);}return null;
}