チェーンテーブルの交差点とループの問題

基本的な問題:
1.2つのチェーンテーブルの最初の共通ノード
[問題を解く考え方]
a.まず2つのチェーンテーブルの長さを求め、チェーンテーブルの長さ差dを得る
b.チェーンテーブルの長さの差により、まず長いチェーンテーブルのポインタをd-1ステップ先に行かせ、その後2つのポインタを一緒に歩かせ、同じノードを発見した場合に共通ノード

    int len1 = 0, len2 = 0;
        ListNode p1 = head1, p2 = head2;
        while (p1 != null) {
            len1++;
            p1 = p1.next;
        }

        while (p2 != null) {
            len2++;
            p2 = p2.next;
        }
        
        ListNode listLong = null, listShort = null;
        int lenDiff = 0; 
        if(len1 > len2){
            listLong = head1;
            listShort = head2;
            lenDiff = len1 - len2;
        } else {
            listLong = head2;
            listShort = head1;
            lenDiff = len2 - len1;
        }
        
        for(int i = 0; i < lenDiff; i++){
            listLong = listLong.next;
        }
        
        while(listLong != null && listShort != null && (listLong != listShort)){
            listLong = listLong.next;
            listShort = listShort.next;
        }

        return listLong;

2.チェーンテーブルにリングがあるかどうかを判断する方法
[問題を解く考え方]
前の問題と同じように、2つのポインタを維持します.1つのポインタは1ステップずつ、もう1つのポインタは2ステップずつ歩いています.速いポインタが遅いポインタに追いつくと、チェーンテーブルにループが存在します.

 1 public static boolean checkCircle2(ListNode head) {
 2         if (head == null) {
 3             return false;
 4         }
 5 
 6         ListNode fast = head, slow = head;
 7         while (fast != null && fast.next != null) {
 8             slow = slow.next;
 9             fast = fast.next.next;
10             if(slow == fast){
11                 break;
12             }
13         }
14         return !(fast == null || fast.next == null);
15     }

 
拡張の問題:
1.問題2の環の入口点を求める
チェーンテーブルにループが存在することを明確に知っていれば,ループでチェーンテーブルを取り外すと,上記の問題1となり,入口ノードを見つけてチェーンテーブルを復元する.

 1 public static ListNode findPortal(ListNode head) {
 2         if (head == null) {
 3             return null;
 4         }
 5 
 6         ListNode fast = head, slow = head;
 7         ListNode head2 = null, tail = null;
 8         while (fast != null && fast.next != null) {
 9             slow = slow.next;
10             fast = fast.next.next;
11             // meet in circle, break the circle
12             if (slow == fast) {
13                 head2 = fast.next;
14                 tail = fast;
15                 fast.next = null;
16                 break;
17             }
18         }
19 
20         ListNode result = findCommonNode(head, head2);
21         tail.next = head2;
22 
23         return result;
24     }
25 
26     private static ListNode findCommonNode(ListNode head1, ListNode head2) {
27         if (head1 == null || head2 == null) {
28             return null;
29         }
30         int len1 = 0, len2 = 0;
31         ListNode p1 = head1, p2 = head2;
32         while (p1 != null) {
33             len1++;
34             p1 = p1.next;
35         }
36 
37         while (p2 != null) {
38             len2++;
39             p2 = p2.next;
40         }
41         
42         ListNode listLong = null, listShort = null;
43         int lenDiff = 0; 
44         if(len1 > len2){
45             listLong = head1;
46             listShort = head2;
47             lenDiff = len1 - len2;
48         } else {
49             listLong = head2;
50             listShort = head1;
51             lenDiff = len2 - len1;
52         }
53         
54         for(int i = 0; i < lenDiff; i++){
55             listLong = listLong.next;
56         }
57         
58         while(listLong != null && listShort != null && (listLong != listShort)){
59             listLong = listLong.next;
60             listShort = listShort.next;
61         }
62 
63         return listLong;
64     }

この問題には別の解題構想がある:http://www.cppblog.com/humanchao/archive/2012/11/12/47357.html
2つのポインタが出会ったときにslowポインタがsステップを歩いたと仮定すると、fastポインタは2 sステップ(遅いポインタが1ステップ、速いポインタが2ステップ)歩いた.
このときfastポインタはnリングを迂回している可能性があります(n>=0)、2 s=s+nr;==>>s = nr;
チェーンテーブルの起点からリングまでの入口点距離をaとし、リング入口点から両ポインタの出会い点距離をx.=>s=a+xとする.
==>a + x = nr;
==>a + x = (n-1)r + r
==>a + x = (n-1)r + L - a
==>a = (n-1)r + L - x -a;
fastポインタとslowポインタが出会ったことを発見したとき、チェーンテーブルのヘッダノードと出会ったノードをそれぞれ指し、同時に歩き始めた2つのポインタを使用して、彼らが出会ったノードは
リングの入口ノード
 

 1 public static ListNode findPortal2(ListNode head) {
 2         if (head == null) {
 3             return null;
 4         }
 5         
 6         ListNode fast = head, slow = head;
 7         while(fast != null && fast.next != null){
 8             fast = fast.next.next;
 9             slow = slow.next;
10             if(fast == slow){
11                 break;
12             }
13         }
14         
15         if(fast == null || fast.next == null){
16             return null;
17         }
18         
19         ListNode p = head;
20         while(p != fast){
21             p = p.next;
22             fast = fast.next;
23         }
24         return p;
25     }

 
 
 
チェーンテーブルのその他の問題:
1.チェーンテーブルの最後からk番目のノードを求める
2.チェーンテーブルの中間ノードを求め、例えばチェーンテーブルの中のノードの総数が奇数で、中間ノードを返す.偶数の場合は、中間の2つのノードのいずれかを返します.
問題のソース:
http://www.cnblogs.com/sooner/p/3277886.html