首先简述一下 哈希表结构 HashMap和HashSet之间关系。HashSet存储的是Map中的key，value不存。
1.打印两个有序链表的公共部分
【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
【思路】外排序，归并排序中的merge过程。谁小谁移动，相等就打印，然后两个指针一起移动。
public class PrintCommonPart {
public static class Node{
public int value;
public Node next;
public Node(int data){
this.value=data;
}
public static void PrintCommonPart01(Node head1,Node head2){
System.out.println("Common Part:");
if(head1==null||head2==null){
return;
}
while(head1!=null&&head2!=null){
if (head1.value<head2.value){
head1=head1.next;
}else if(head1.value>head2.value){
head2=head2.next;
}else {
System.out.println(head1.value);
head1=head1.next;
head2=head2.next;
}
System.out.println();
}
}
}
}
2.判断一个链表是否为回文结构
【题目】 给定一个链表的头节点head，请判断该链表是否为回 文结构。 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。
进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
【思路】
1.笔试使用，使用一个栈，需要n个额外空间。将链表的节点依次纳入一个栈，再从栈顶依次弹出节点，与链表节点依次比对，有一个不相同，返回false。
2.使用栈和快慢指针，需要n/2额外空间。快指针一次走两步，慢指针一次走一步，当快指针走到链表尾部时，慢指针走到链表的中部。将慢指针此时指向的节点和后续的节点压入栈，再从栈顶依次弹出节点，与链表节点依次比对，有一个不相同，返回false。
3.面试使用，使用快慢指针和原地逆序链表，需要O(1)个额外空间。从中间节点后原地逆序链表，再从尾节点依次与头节点处对比，有一个不相同，返回false。最后需要还原逆序后的链表。
//判断一个链表是否为回文结构
//给定一个链表的头节点head，请判断该链表是否为回文结构。
// 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。
public class IsPalindromeList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
//使用一个栈 需要n额外空间 笔试使用
public static boolean isPalindromeList01(Node head){
Stack<Node> stack=new Stack<>();
Node cur=head;
while (cur!=null){
stack.push(cur);
cur=cur.next;
}
while(!stack.isEmpty()){
if (stack.pop().value!=head.value){
return false;
}
head=head.next;
}
return true;
}
//使用栈和快慢指针 需要n/2额外空间
public static boolean isPalindromeList02(Node head){
if(head==null||head.next==null){
return true;
}
Node right=head.next;
Node cur=head;
while(cur.next!=null&&cur.next.next!=null){
right=right.next;
cur=cur.next.next;
}
//压栈
Stack<Node> stack=new Stack<Node>();
while (right!=null){
stack.push(right);
right=right.next;
}
while (!stack.isEmpty()){
if (stack.pop().value!=head.value){
return false;
}
head=head.next;
}
return true;
}
//使用快慢指针和原地逆序链表，需要O(1)个额外空间
public static boolean isPalindromeList03(Node head){
if (head==null||head.next==null){
return true;
}
Node n1=head;
Node n2=head;
while (n2.next!=null&&n2.next.next!=null){ // find mid node
n1=n1.next; // n1 -> mid
n2=n2.next.next; // n2 -> end
}
//原地逆序链表
n2=n1.next;//n2->right part first node
n1.next=null;//mid.next -> null
Node n3=null;
while (n2!=null){ //right part convert
n3=n2.next; //n3 ->save next Node
n2.next=n1; //next of right node convert
n1=n2; // n1 move
n2=n3; //n2 move
}
//从左至中间 和从右至中间 依次对比
n3=n1;//n3-> save last node
n2=head;//n2-> left first node
boolean res=true;
while (n1!=null &&n2!=null){
if(n1.value!=n2.value){
res =false;
break;
}
n1=n1.next;//left to mid
n2=n2.next;//right to mid
}
n1=n3.next;
n3.next=null;
while (n1!=null){ //recover list
n2=n1.next;
n1.next=n3;
n3=n1;
n1=n2;
}
return res;
}
3.将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个 整 数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5>1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总 之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部 分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
进阶： 在原问题的要求之上再增加如下两个要求。 在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的 顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再 讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 最后出现5。 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
【思路】
1.（1）荷兰国旗问题，但是不稳定。
将节点放在一个数组中，使用解决荷兰国旗问题的思路(划分)去解决。
最后要重新连接数组中的节点。
- （1）具有稳定性。
设置三个链表，将原链表中的所有节点依次划分进这三个链表，三个链表分别为small代表左部分，equal代表中间部分，big代表右部分。
（2）将small、equal、big三个链表重新串起来即可。
整个过程需要特别注意对null节点的判断和处理。
public class SmallerEqualBigger {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
//1.荷兰国旗问题，但是不稳定。
//将节点放在一个数组中，使用解决荷兰国旗问题的思路(划分)去解决。
//最后要重新连接数组中的节点
public static Node listPartition1(Node head,int pivot){
if(head==null){
return head;
}
Node cur=head;
int i=0;
while (cur!=null){
i++;
cur=cur.next;
}
Node [] nodeArr=new Node[i];
i=0;
cur=head;
for (i=0;i<nodeArr.length;i++){
nodeArr[i]=cur;
cur=cur.next;
}
arrPartition(nodeArr,pivot);
//荷兰国旗划分好 将链表重新连接
for(i=1;i<nodeArr.length;i++){
nodeArr[i-1].next=nodeArr[i];
}
//最后一个节点指向空
nodeArr[i-1].next=null;
return nodeArr[0];
}
//荷兰国旗问题的解决思路
private static void arrPartition(Node[] nodeArr, int pivot) {
int small=-1;
int big=nodeArr.length;
int index=0;
while (index<big){
if (nodeArr[index].value<pivot){
swap(nodeArr,++small,index++);
}else if (nodeArr[index].value>pivot){
swap(nodeArr,--big,index);
}else {
index++;
}
}
}
private static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
//1.设置三个链表，将原链表中的所有节点依次划分进这三个链表，
// 三个链表分别为small代表左部分，equal代表中间部分，big代表右部分。
//2.将small、equal、big三个链表重新串起来即可。
//整个过程需要特别注意对null节点的判断和处理。
public static Node listPartition2(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;//bug tail
Node next=null;//save next node
// every node distributed to three lists
while(head!=null){
next=head.next;
head.next=null;
if (head.value<pivot){
if (sH==null){
sH=head;
sT=head;
}else {
sT.next=head;
sT=sT.next;
}
}else if (head.value==pivot){
if (eH==null){
eH=head;
eT=head;
}else{
eT.next=head;
eT=eT.next;
}
}else {
if (bH==null){
bH=head;
bT=head;
}else {
bT.next=head;
bT=bT.next;
}
}
head = next;
}
// small and equal reconnect
if (sT!=null){
sT.next=eH;
eT=eT==null?sT:eT;
}
//all connect
if (eT!=null){
eT.next=bH;
}
return sH!=null? sH:eH!=null?eH:bH;
}
4.复制含有随机指针节点的链表
【题目】 一种特殊的链表节点类描述如下： public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } Node类中的value是节点值，next指针和正常单链表中next指针的意义一样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。 给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。 进阶： 不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N) 内完成原问题要实现的函数。
【思路】1.使用hashMap去复制原始链表，第一次遍历进行节点的复制，第二次遍历记录节点的指针指向，从而设置副本节点的next和rand指针。最后返回副本节点的头节点。
2.第一次遍历，在每一个节点后面生成一个复制节点，再连接上下一个节点，形成1->1'->2->2'->3->3'->null的结构；第二次遍历，设置副本节点的next和rand指针；最后进行分离产生副本链表。
package LinkList;
//一种特殊的链表节点类描述如下：
// public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } }
// Node类中的value是节点值，next指针和正常单链表中next指针的意义 一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指 针可 能指向链表中的任意一个节点，也可能指向null。
// 给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个函数完成 这个链表中所有结构的复制，并返回复制的新链表的头节点。
// 进阶： 不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N) 内完成原问题要实现的函数。
import java.util.HashMap;
public class CopyListWithRandom {
public static class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
//1 定义一个哈希表
//2 遍历一次链表，将节点进行复制
//3 遍历一次链表，将节点的指针指向进行记录
public static Node copyListWithRand1(Node head) {
HashMap<Node,Node> map=new HashMap<Node,Node>() ;
Node cur=head;
while (cur!=null){
map.put(cur,new Node(cur.value));
cur=cur.next;
}
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);
}
public static Node copyListWithRand2(Node head){
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// copy node and link to every node
//1->1'->2->2'->3->3'->null
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// set copy node rand
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
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;
}
5.两个单链表相交的一系列问题
【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；如果不相交，返回null 即可。 要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)。
【思路】本题第一步要判断的是单链表是否有环，此问题在之前已有论述。该函数返回的是有环单链表的第一个入环节点。
判断单链表是否有环介绍以下两种思路：1.使用哈希表，只需要存map中的key，不需要存map中的value，即使用hashSet。当遍历到一个元素在hashSet中已经存在了，即该节点为第一个入环节点。2.使用快慢指针法，快指针一次走两步，慢指针一次走一步，两者相遇时，快指针回到head并此后每次走一步，当这两个指针再次相遇时，相遇的节点 就是第一个入环节点。
如果一个链表为空，直接返回null
都不空的情况下，首先判断A,B两个单链表是否有环。分以下几种情况：
1.A,B 都没有环，找到两个单链表的相交节点。
2.A,B都有环，有3种情况。一种不相交，一种Y+O,一种小电视。
3. A,B有一个有环，有一个无环，则不存在相交节点。
1中
public class FindFirstIntersectNode {
//如果一个链表为空，直接返回null
//都不空的情况下，首先判断A,B两个单链表是否有环。分以下几种情况：
//1.A ，B 都没有环，找到两个单链表的相交节点。
//2.A,B都有环，有3种情况。一种不相交，一种Y+O,一种小电视。
//3. A,B有一个有环，有一个无环，则不存在相交节点。
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;
}
//2.A,B都有环，有3种情况。一种不相交，一种Y+O,一种小电视。
private static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2) {
Node cur1 = null;
Node cur2 = null;
//判断的关键在于是否loop1==loop2，如果相等则是Y+O,和两个无环链表相交问题一样
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;
}
}
//1.A ，B 都没有环，找到两个单链表的相交节点。
//方法1：使用hashMap,先把A放到map中，再B中节点一个一个检查map中是否已经存在。
//方法2;首先遍历一次A，记录下链表长度length1以及最后一个节点是什么end1；
// 再遍历一次B，记录下链表长度length1以及最后一个节点是什么end2;
//如果end1！=end2，说明这两个单链表都不相交；
//如果end1==end2，用length长的的那个链表先走|length1-length2|，再两个链表一起走，相遇即是第一个相交节点。
private 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;
}
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;
}
//该方法返回链表的第一个入环节点，如果有环则返回入环的第一个节点，否则返回null
public static Node getLoopNode(Node head){
if(head==null||head.next==null||head.next.next==null){
return null;
}
Node slow=head.next;
Node fast=head.next.next;
while (slow!=fast){
if (fast.next==null||fast.next.next==null){
return null;
}
slow=slow.next;
fast=fast.next.next;
}
fast=head;//快指针又回到开头
while (slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
