首先簡述一下 哈希表結(jié)構(gòu) HashMap和HashSet之間關(guān)系过吻。HashSet存儲(chǔ)的是Map中的key，value不存乳绕。
1.打印兩個(gè)有序鏈表的公共部分
【題目】 給定兩個(gè)有序鏈表的頭指針head1和head2洋措，打印兩個(gè)鏈表的公共部分杰刽。
【思路】外排序，歸并排序中的merge過程滓鸠。誰小誰移動(dòng)糜俗，相等就打印，然后兩個(gè)指針一起移動(dòng)珠月。
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.判斷一個(gè)鏈表是否為回文結(jié)構(gòu)
【題目】 給定一個(gè)鏈表的頭節(jié)點(diǎn)head啤挎，請(qǐng)判斷該鏈表是否為回 文結(jié)構(gòu)庆聘。 例如： 1->2->1氛谜，返回true值漫。 1->2->2->1织盼，返回true沥邻。 15->6->15唐全，返回true。 1->2->3弥雹，返回false延届。
進(jìn)階： 如果鏈表長度為N方庭，時(shí)間復(fù)雜度達(dá)到O(N)，額外空間復(fù)雜 度達(dá)到O(1)头朱。
【思路】
1.筆試使用髓窜，使用一個(gè)棧，需要n個(gè)額外空間鳖敷。將鏈表的節(jié)點(diǎn)依次納入一個(gè)棧定踱，再從棧頂依次彈出節(jié)點(diǎn)恃鞋，與鏈表節(jié)點(diǎn)依次比對(duì)恤浪，有一個(gè)不相同水由，返回false。
2.使用棧和快慢指針泥张，需要n/2額外空間鞠值⊥瘢快指針一次走兩步声离，慢指針一次走一步，當(dāng)快指針走到鏈表尾部時(shí)焕议，慢指針走到鏈表的中部盅安。將慢指針此時(shí)指向的節(jié)點(diǎn)和后續(xù)的節(jié)點(diǎn)壓入棧，再從棧頂依次彈出節(jié)點(diǎn)窿祥，與鏈表節(jié)點(diǎn)依次比對(duì)晒衩，有一個(gè)不相同墙歪，返回false虹菲。
3.面試使用，使用快慢指針和原地逆序鏈表浪漠，需要O(1)個(gè)額外空間址愿。從中間節(jié)點(diǎn)后原地逆序鏈表响谓，再從尾節(jié)點(diǎn)依次與頭節(jié)點(diǎn)處對(duì)比俱饿，有一個(gè)不相同拍埠，返回false土居。最后需要還原逆序后的鏈表擦耀。
//判斷一個(gè)鏈表是否為回文結(jié)構(gòu)
//給定一個(gè)鏈表的頭節(jié)點(diǎn)head眷蜓，請(qǐng)判斷該鏈表是否為回文結(jié)構(gòu)。
// 例如： 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;
}
}
//使用一個(gè)棧 需要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)個(gè)額外空間
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
}
//從左至中間 和從右至中間 依次對(duì)比
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.將單向鏈表按某值劃分成左邊小吞杭、中間相等芽狗、右邊大的形式
【題目】 給定一個(gè)單向鏈表的頭節(jié)點(diǎn)head痒蓬，節(jié)點(diǎn)的值類型是整型，再給定一個(gè) 整 數(shù)pivot顾复。實(shí)現(xiàn)一個(gè)調(diào)整鏈表的函數(shù)芯砸，將鏈表調(diào)整為左部分都是值小于 pivot 的節(jié)點(diǎn)，中間部分都是值等于pivot的節(jié)點(diǎn)末购，右部分都是值大于 pivot的節(jié)點(diǎn)盟榴。 除這個(gè)要求外婴噩，對(duì)調(diào)整后的節(jié)點(diǎn)順序沒有更多的要求几莽。 例如：鏈表9->0->4->5>1章蚣，pivot=3纤垂。 調(diào)整后鏈表可以是1->0->4->9->5，也可以是0->1->9->5->4贾虽∨罨恚總 之菇肃，滿 足左部分都是小于3的節(jié)點(diǎn)琐谤，中間部分都是等于3的節(jié)點(diǎn)（本例中這個(gè)部 分為空）笑跛，右部分都是大于3的節(jié)點(diǎn)即可飞蹂。對(duì)某部分內(nèi)部的節(jié)點(diǎn)順序不做要求翻屈。
進(jìn)階： 在原問題的要求之上再增加如下兩個(gè)要求。 在左刽宪、中圣拄、右三個(gè)部分的內(nèi)部也做順序要求毁欣，要求每部分里的節(jié)點(diǎn)從左 到右的 順序與原鏈表中節(jié)點(diǎn)的先后次序一致凭疮。 例如：鏈表9->0->4->5->1执解，pivot=3。 調(diào)整后的鏈表是0->1->9->4->5新蟆。 在滿足原問題要求的同時(shí)栅葡，左部分節(jié)點(diǎn)從左到 右為0欣簇、1熊咽。在原鏈表中也 是先出現(xiàn)0闹丐，后出現(xiàn)1卿拴；中間部分在本例中為空堕花，不再 討論缘挽；右部分節(jié)點(diǎn) 從左到右為9呻粹、4等浊、5筹燕。在原鏈表中也是先出現(xiàn)9衅鹿，然后出現(xiàn)4塘安， 最后出現(xiàn)5兼犯。 如果鏈表長度為N切黔，時(shí)間復(fù)雜度請(qǐng)達(dá)到O(N)纬霞，額外空間復(fù)雜度請(qǐng)達(dá)到O(1)。
【思路】
1.（1）荷蘭國旗問題瞳抓，但是不穩(wěn)定孩哑。
將節(jié)點(diǎn)放在一個(gè)數(shù)組中横蜒，使用解決荷蘭國旗問題的思路(劃分)去解決丛晌。
最后要重新連接數(shù)組中的節(jié)點(diǎn)澎蛛。
- （1）具有穩(wěn)定性孟岛。
設(shè)置三個(gè)鏈表渠羞，將原鏈表中的所有節(jié)點(diǎn)依次劃分進(jìn)這三個(gè)鏈表次询，三個(gè)鏈表分別為small代表左部分屯吊，equal代表中間部分盒卸，big代表右部分蔽介。
（2）將small虹蓄、equal薇组、big三個(gè)鏈表重新串起來即可。
整個(gè)過程需要特別注意對(duì)null節(jié)點(diǎn)的判斷和處理宋光。
public class SmallerEqualBigger {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
//1.荷蘭國旗問題跃须，但是不穩(wěn)定菇民。
//將節(jié)點(diǎn)放在一個(gè)數(shù)組中第练，使用解決荷蘭國旗問題的思路(劃分)去解決娇掏。
//最后要重新連接數(shù)組中的節(jié)點(diǎn)
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];
}
//最后一個(gè)節(jié)點(diǎn)指向空
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.設(shè)置三個(gè)鏈表下梢，將原鏈表中的所有節(jié)點(diǎn)依次劃分進(jìn)這三個(gè)鏈表孽江，
// 三個(gè)鏈表分別為small代表左部分岗屏，equal代表中間部分这刷，big代表右部分暇屋。
//2.將small率碾、equal所宰、big三個(gè)鏈表重新串起來即可畜挥。
//整個(gè)過程需要特別注意對(duì)null節(jié)點(diǎn)的判斷和處理。
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.復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表
【題目】 一種特殊的鏈表節(jié)點(diǎn)類描述如下： public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } Node類中的value是節(jié)點(diǎn)值蟹但，next指針和正常單鏈表中next指針的意義一樣躯泰，都指向下一個(gè)節(jié)點(diǎn)，rand指針是Node類中新增的指針华糖，這個(gè)指針可能指向鏈表中的任意一個(gè)節(jié)點(diǎn)麦向，也可能指向null。 給定一個(gè)由 Node節(jié)點(diǎn)類型組成的無環(huán)單鏈表的頭節(jié)點(diǎn)head客叉，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)完成這個(gè)鏈表中所有結(jié)構(gòu)的復(fù)制诵竭，并返回復(fù)制的新鏈表的頭節(jié)點(diǎn)兼搏。 進(jìn)階： 不使用額外的數(shù)據(jù)結(jié)構(gòu)卵慰，只用有限幾個(gè)變量，且在時(shí)間復(fù)雜度為 O(N) 內(nèi)完成原問題要實(shí)現(xiàn)的函數(shù)佛呻。
【思路】1.使用hashMap去復(fù)制原始鏈表裳朋，第一次遍歷進(jìn)行節(jié)點(diǎn)的復(fù)制，第二次遍歷記錄節(jié)點(diǎn)的指針指向吓著，從而設(shè)置副本節(jié)點(diǎn)的next和rand指針鲤嫡。最后返回副本節(jié)點(diǎn)的頭節(jié)點(diǎn)送挑。
2.第一次遍歷，在每一個(gè)節(jié)點(diǎn)后面生成一個(gè)復(fù)制節(jié)點(diǎn)暖眼，再連接上下一個(gè)節(jié)點(diǎn)惕耕，形成1->1'->2->2'->3->3'->null的結(jié)構(gòu)；第二次遍歷罢荡，設(shè)置副本節(jié)點(diǎn)的next和rand指針赡突；最后進(jìn)行分離產(chǎn)生副本鏈表对扶。
package LinkList;
//一種特殊的鏈表節(jié)點(diǎn)類描述如下：
// public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } }
// Node類中的value是節(jié)點(diǎn)值区赵，next指針和正常單鏈表中next指針的意義 一 樣，都指向下一個(gè)節(jié)點(diǎn)浪南，rand指針是Node類中新增的指針笼才，這個(gè)指 針可 能指向鏈表中的任意一個(gè)節(jié)點(diǎn)，也可能指向null络凿。
// 給定一個(gè)由 Node節(jié)點(diǎn)類型組成的無環(huán)單鏈表的頭節(jié)點(diǎn)head骡送，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)完成 這個(gè)鏈表中所有結(jié)構(gòu)的復(fù)制，并返回復(fù)制的新鏈表的頭節(jié)點(diǎn)絮记。
// 進(jìn)階： 不使用額外的數(shù)據(jù)結(jié)構(gòu)摔踱，只用有限幾個(gè)變量，且在時(shí)間復(fù)雜度為 O(N) 內(nèi)完成原問題要實(shí)現(xiàn)的函數(shù)怨愤。
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 定義一個(gè)哈希表
//2 遍歷一次鏈表派敷，將節(jié)點(diǎn)進(jìn)行復(fù)制
//3 遍歷一次鏈表，將節(jié)點(diǎn)的指針指向進(jìn)行記錄
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.兩個(gè)單鏈表相交的一系列問題
【題目】 在本題中撰洗，單鏈表可能有環(huán)篮愉，也可能無環(huán)。給定兩個(gè)單鏈表的頭節(jié)點(diǎn) head1和head2差导，這兩個(gè)鏈表可能相交试躏，也可能 不相交。請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)设褐， 如果兩個(gè)鏈表相交颠蕴，請(qǐng)返回相交的 第一個(gè)節(jié)點(diǎn)；如果不相交助析，返回null 即可裁替。 要求：如果鏈表1 的長度為N，鏈表2的長度為M貌笨，時(shí)間復(fù)雜度請(qǐng)達(dá)到 O(N+M)弱判，額外 空間復(fù)雜度請(qǐng)達(dá)到O(1)。
【思路】本題第一步要判斷的是單鏈表是否有環(huán)锥惋，此問題在之前已有論述昌腰。該函數(shù)返回的是有環(huán)單鏈表的第一個(gè)入環(huán)節(jié)點(diǎn)开伏。
判斷單鏈表是否有環(huán)介紹以下兩種思路：1.使用哈希表，只需要存map中的key遭商，不需要存map中的value固灵，即使用hashSet。當(dāng)遍歷到一個(gè)元素在hashSet中已經(jīng)存在了劫流，即該節(jié)點(diǎn)為第一個(gè)入環(huán)節(jié)點(diǎn)巫玻。2.使用快慢指針法，快指針一次走兩步祠汇，慢指針一次走一步仍秤，兩者相遇時(shí)，快指針回到head并此后每次走一步可很，當(dāng)這兩個(gè)指針再次相遇時(shí)诗力，相遇的節(jié)點(diǎn) 就是第一個(gè)入環(huán)節(jié)點(diǎn)。
如果一個(gè)鏈表為空我抠，直接返回null
都不空的情況下苇本，首先判斷A,B兩個(gè)單鏈表是否有環(huán)。分以下幾種情況：
1.A,B 都沒有環(huán)菜拓，找到兩個(gè)單鏈表的相交節(jié)點(diǎn)瓣窄。
2.A,B都有環(huán)，有3種情況纳鼎。一種不相交俺夕，一種Y+O,一種小電視。
3. A,B有一個(gè)有環(huán)喷橙，有一個(gè)無環(huán)啥么，則不存在相交節(jié)點(diǎn)。
1中
public class FindFirstIntersectNode {
//如果一個(gè)鏈表為空贰逾，直接返回null
//都不空的情況下悬荣，首先判斷A,B兩個(gè)單鏈表是否有環(huán)。分以下幾種情況：
//1.A 疙剑，B 都沒有環(huán)氯迂，找到兩個(gè)單鏈表的相交節(jié)點(diǎn)。
//2.A,B都有環(huán)言缤，有3種情況嚼蚀。一種不相交，一種Y+O,一種小電視管挟。
//3. A,B有一個(gè)有環(huán)轿曙，有一個(gè)無環(huán)，則不存在相交節(jié)點(diǎn)。
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都有環(huán)导帝，有3種情況守谓。一種不相交，一種Y+O,一種小電視您单。
private static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2) {
Node cur1 = null;
Node cur2 = null;
//判斷的關(guān)鍵在于是否loop1==loop2斋荞，如果相等則是Y+O,和兩個(gè)無環(huán)鏈表相交問題一樣
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 都沒有環(huán)平酿，找到兩個(gè)單鏈表的相交節(jié)點(diǎn)。
//方法1：使用hashMap,先把A放到map中悦陋，再B中節(jié)點(diǎn)一個(gè)一個(gè)檢查map中是否已經(jīng)存在蜈彼。
//方法2;首先遍歷一次A，記錄下鏈表長度length1以及最后一個(gè)節(jié)點(diǎn)是什么end1叨恨；
// 再遍歷一次B柳刮，記錄下鏈表長度length1以及最后一個(gè)節(jié)點(diǎn)是什么end2;
//如果end1挖垛！=end2痒钝，說明這兩個(gè)單鏈表都不相交；
//如果end1==end2痢毒，用length長的的那個(gè)鏈表先走|length1-length2|送矩，再兩個(gè)鏈表一起走，相遇即是第一個(gè)相交節(jié)點(diǎn)哪替。
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;
}
//該方法返回鏈表的第一個(gè)入環(huán)節(jié)點(diǎn)栋荸，如果有環(huán)則返回入環(huán)的第一個(gè)節(jié)點(diǎn)，否則返回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;
}
