1 class NodeMake{
  2     constructor(){
  3         this.value=null;
  4         this.next=null;
  5     }
  6 }
  7 //随机指针节点
  8 class NodeMakeRandom{
  9     constructor(){
 10         this.value=null;
 11         this.next=null;
 12         this.random=null;
 13     }
 14     Clone(Node){
 15         this.value=Node.value;
 16         this.next=Node.next;
 17         this.random=Node.random;
 18     }
 19 }
 20 function MakeLink(){
 21     let head=new NodeMake();
 22     for(let i=0;i<=5;i++){
 23         let tmpval= Math.floor(Math.random()*10);
 24         let p= new NodeMake();
 25         p.value=tmpval;
 26         p.next=head.next;
 27         head.next=p;
 28     }
 29 
 30     return head.next;
 31 }
 32 
 33 function output(head){
 34     let p=head;
 35     while(p){
 36         console.log(p.value);
 37         p=p.next;
 38     }
 39 }
 40 //用头插法实现反转链表
 41 function ReverseLink(head){
 42     if(head.next==null){
 43         return head;
 44     }
 45     let new_head=new NodeMake();
 46     let p=head;
 47     while(p){
 48         let tmp=p.next;
 49         p.next=new_head.next
 50         new_head.next=p;
 51         p=tmp;
 52     }
 53     return new_head.next;
 54 
 55 }
 56 //判断回文，用压栈方式快速解决
 57 function JudegePal1(head){
 58     let stack =new Array();
 59     let p=head;
 60     while(p){
 61         if(p.value==stack[0]){
 62             stack.shift();
 63         }
 64         else{
 65             stack.unshift(p.value);
 66         }
 67         p=p.next;
 68     }
 69     if(stack.length==0||stack.length==1){
 70         console.log("是回文");
 71     }
 72     else{
 73         console.log("不是回文");
 74     }
 75 
 76 }
 77 //判断回文，用快慢指针减少空间复杂度
 78 function JudegePal2(head){
 79     let slow=head;
 80     let fast=head;
 81     while(fast&&fast.next){
 82         slow=slow.next;
 83         fast=fast.next.next;
 84     }
 85     //若链表只有一个值时返回
 86     if(fast==head){
 87         console.log("是回文");
 88         return;
 89     }
 90     //从slow节点反转链表，从首尾逼近比较
 91     let Tail=ReverseLink(slow);
 92     let FromTail=Tail;
 93     let FromHead=head;
 94     let flag=1;
 95     while(FromHead&&FromTail){
 96         if(FromHead.value!=FromTail.value){
 97             flag=0;
 98             break;
 99         }
100         FromHead=FromHead.next;
101         FromTail=FromTail.next;
102     }
103     ReverseLink(Tail);
104     if(flag){
105         console.log("是回文");
106     }
107     else{
108         console.log("不是回文");
109     }
110 
111 
112 }
113 //单链表的荷兰国旗问题
114 //用数组快速解决
115 function LessEqualMore1(head,num){
116     let arr=new Array();
117     let p=head;
118     while(p){
119         arr.push(p);
120         p=p.next;
121     }
122     GuoQi(arr,num);
123     head=arr[0];
124     let i;
125     for(i=0;i<=arr.length-2;i++){
126         arr[i].next=arr[i+1];
127     }
128     arr[i].next=null;
129 }
130 function GuoQi(arr,num){
131     let less,more,i;
132     less=-1;more=arr.length;i=0;
133     while(i<more){
134         if(arr[i].value<num){
135             less++;
136             swap(arr,i,less);
137             i++;
138         }
139         else if(arr[i].value>num){
140             more--;
141             swap(arr,i,more);
142         }
143         else{
144             i++;
145         }
146     }
147 }
148 function swap(arr,p1,p2){
149     [arr[p1],arr[p2]]=[arr[p2],arr[p1]];
150 }
151 //用六个变量标志各个区域头尾，减少空间复杂度
152 function LessEqualMore2(head,num){
153     let LessStart,LessEnd,EqualStart,EqualEnd,MoreStart,MoreEnd;
154     let p=head;
155     let new_head;
156     while(p){
157         if(p.value<num){
158             let tmp=p;
159             p=p.next;
160             if(LessStart==null){
161                 LessStart=tmp;
162                 LessEnd=tmp;
163                 LessEnd.next=null;
164                 continue;
165             }
166             let sign=LessEnd;
167             LessEnd=tmp;
168             sign.next=LessEnd;
169             LessEnd.next=null;
170         }
171         else if(p.value>num){
172             let tmp=p;
173             p=p.next;
174             if(MoreStart==null){
175                 MoreStart=tmp;
176                 MoreEnd=tmp;
177                 MoreEnd.next=null;
178                 continue;
179             }
180             let sign=MoreEnd;
181             MoreEnd=tmp;
182             sign.next=MoreEnd;
183             MoreEnd.next=null;
184         }
185         else{
186             let tmp=p;
187             p=p.next;
188             if(EqualStart==null){
189                 EqualStart=tmp;
190                 EqualEnd=tmp;
191                 EqualEnd.next=null;
192                 continue;
193             }
194             let sign =EqualEnd;
195             EqualEnd=tmp;
196             sign.next=EqualEnd;
197             EqualEnd.next=null;
198         }
199         
200     }
201     if(LessStart){
202         if(EqualStart){
203             LessEnd.next=EqualStart;
204             EqualEnd.next=MoreStart;
205         }
206         else{
207             LessEnd.next=MoreStart;
208         }
209         new_head=LessStart;
210     }
211     else if(EqualStart){
212         EqualEnd.next=MoreStart;
213         new_head=EqualStart;
214     }
215     else{
216         new_head=MoreStart;
217     }
218     return new_head;
219 }
220 //随即指针链表的复制
221 //用哈希表快速解决
222 function CopyLink1(head){
223     let p=head;
224     let HashMap=new Map();
225     while(p){
226         let clone=p;
227         HashMap.set(p,clone);
228         p=p.next;
229     }
230     p=head;
231     while(p){
232         let clone=HashMap.get(p);
233         clone.next=HashMap.get(p.next);
234         clone.random=HashMap.get(p.random);
235         p=p.next;
236     }
237     return HashMap.get(head);
238 }
239 //用克隆节点直接挂节省空间
240 function CopyLink2(head){
241     let p=head;
242     while(p){
243         let sign=p;
244         p=p.next;
245         let clone=new NodeMakeRandom;
246         clone.Clone(sign);
247         sign.next=clone;
248         clone.next=p;
249     }
250     p=head;
251     let new_head;
252     new_head=p.next;
253     let tmp=new_head;
254     while(p){
255         let sign=p;
256         p=p.next.next;
257         if(tmp.random){
258             tmp.random=tmp.random.next;
259         }
260         if(p){
261             tmp.next=p.next;
262             tmp=tmp.next;
263         }
264         sign.next=p;
265     }
266     return new_head;
267 
268 }
269 //判断两个有可能有环的单链表是否相交
270 function JudgeIntersect(head1,head2){
271     let loop1,loop2;
272     loop1=JudgeLoop(head1);loop2=JudgeLoop(head2);
273     //一个有环一个无环的单链表是不可能有交点的
274     if((loop1==null&&loop2!=null)||(loop1!=null&&loop2==null)){
275         console.log("没有交点");
276         return;
277     }
278     else if(loop1==null&&loop2==null){//两个无环的单链表
279         let end1,end2,length;
280         end1=head1;end2=head2;length=0;
281         while(end1.next){
282             end1=end1.next;
283             length++;
284         }
285         while(end2.next){
286             end2=end2.next;
287             length--;
288         }
289         if(end1!=end2){//终点不同的两个单链表是不会有交点的
290             console.log("没有交点");
291             return;
292         }
293         else{
294             let cur1=length>=0?head1:head2;//cur1存放长的那个链表
295             let cur2=cur1==head1?head2:head1;
296             length=Math.abs(length);
297             for(let i=1;i<=length;i++){
298                 cur1=cur1.next;
299             }
300             while(cur1!=cur2){
301                 cur1=cur1.next;
302                 cur2=cur2.next;
303             }
304             console.log("交点是"+cur1.value);
305             return ;
306         }
307     }
308     else{//两个有环的单链表
309         if(loop1==loop2){//环的第一个点相同，相当于两个无环单链表
310             let end1,end2,length;
311             end1=head1;end2=head2;
312             while(end1!=loop1.next){
313                 end1=end1.next;
314                 length++;
315             }
316             while(end2!=loop1.next){
317                 end2=end2.next;
318                 length--;
319             }
320             let cur1=length>=0?head1:head2;//cur1存放长的那个链表
321             let cur2=cur1==head1?head2:head1;
322             length=Math.abs(length);
323             for(let i=1;i<=length;i++){
324                 cur1=cur1.next;
325             }
326             while(cur1!=cur2){
327                 cur1=cur1.next;
328                 cur2=cur2.next;
329             }
330             console.log("交点是"+cur1.value);
331             return 
332         }
333         else{//快慢指针判断交点不同的情况
334             let time=0;
335             let slow,fsat;
336             slow=loop1.next;fast=loop2.next.next;
337             while(slow!=fast){
338                 if(fast==loop2||fast.next==loop2){
339                     time++;
340                 }
341                 if(time>=3){
342                     console.log("没有交点");
343                     return;
344                 }
345                 slow=slow.next;fast=fast.next.next;
346             }
347             console.log("两个交点"+loop1.value+loop2.value);
348             return;
349         }
350 
351     }
352 
353 }
354 //快慢指针判断单链表有无环
355 function JudgeLoop(head){
356     if(head.next==null){
357         return null;
358     }
359     let slow,fast;
360     slow=head.next;fast=head.next.next;
361     while(slow!=fast){
362         slow=slow.next;
363         if(fast&&fast.next){
364             fast=fast.next.next;
365         }
366         else{
367             console.log("无环");
368             return null;
369         }
370     }
371     fast=head;
372     while(slow!=fast){
373         slow=slow.next;
374         fast=fast.next;
375     }
376     console.log("环的第一个点是"+slow.value);
377     return slow;
378 }
379 
380 //一些测试数据
381 let head1=MakeLink();
382 let head2=MakeLink();
383 //output(head);
384 // JudegePal2(head);
385 //LessEqualMore1(head,2);
386 // output(head);
387 // console.log("*************");
388 // // JudegePal1(head);
389 // head=LessEqualMore2(head,2);
390 // head.random=head.next.next;
391 // console.log("*************");
392 // head = CopyLink2(head);
393 // output(head);
394 // output(head.random);
395 // output(head1);
396 // console.log("*************");
397 // output(head2);
398 head1.next.next.next.next=head2.next;
399 head2.next.next.next.next=head1.next;
400 // output(head1);
401 // console.log("*************");
402 // output(head2);
403 JudgeIntersect(head1,head2);