プログラミング問題-チェーンテーブルとデュアルポインタ

まとめ:チェーンテーブルに関する問題の大部分はダブルポインタで解決できます.i.e.,チェーンテーブルの最後からk番目のノードを探し,チェーンテーブルの中間1/2ノードを探し,チェーンテーブルにリングがあるかどうかを検出する.スナップポインタ
1、チェーンテーブルの最後からk番目のノードを探す[1]
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.多くの人の習慣に合うように、本題は1から数え始めます.すなわち、チェーンテーブルの末尾ノードは最後から1番目のノードです.たとえば、チェーンテーブルには6つのノードがあり、先頭ノードから1、2、3、4、5、6の順に値が表示されます.このチェーンテーブルの最後から3番目のノードは4のノードです.
/*ダブルポインタ
1)p 1はp 2より先にk−1ステップ進み、p 1が最後のノードに達すると、p 2は最後からk番目のノードを指す
2)p 1はp 2より先にk歩進み、p 1が最終終点(NULL)に達すると、p 2は最後からk番目のノードを指す
*/
コード:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        /*   
        p1 p2  k-1 
        */
        ListNode* p1 = head;
        ListNode* p2 = head;
        //p1  k-1 
        int step = 0;
        while (stepnext;
        }

        if (!p1) return NULL;

        while (p1->next)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2;
    }
};

2、チェーンテーブルの中間ノード[2]
ヘッダノードheadを有する非空の単一チェーンテーブルが与えられ、チェーンテーブルの中間ノードが戻される.
中間ノードが2つある場合は、2番目の中間ノードを返します.
考え方:高速ポインタ、高速ポインタp 2は一度に2歩、遅いポインタp 1は一度に1歩歩く.
特殊な処理が必要なのは、偶数ノードが2番目の中間ノードを出力することです.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if (!head)
            return head;
        ListNode* p1 = head, *p2=head;
        
        while (p2->next)
        {
            p1 = p1->next;
            p2 = p2->next;
            if (p2->next)
                p2 = p2->next;
        }
        return p1;

    }
};

3、リングチェーン[3]
チェーンテーブルにループがあるかどうかを判断し、ループがある場合は、ループの開始点を見つけます.
考え方:
1)リングがあるかどうかを確定して、速い遅いポインタ、速いポインタ*fastは毎回2歩(あるいは多歩)移動して、遅いポインタ*slowは毎回1歩移動して、もしリングが存在するならば、両者はきっとリングの上で出会って、しかも出会った時に遅いポインタはまだ1周を歩き終わっていません(leetcode公式の問題解を証明します);そうでなければリングがありません.
2)ループがあることを確認し(スナップポインタが出会った後)、そのうちの1つをチェーンテーブルの始点headに移動し、その後、両者は毎回1ステップ移動し、出会い点は入ループの始点となる.
c++コード

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head)
            return head;
        ListNode *fast = head, *slow=head;
        while (fast->next&&fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) //  ，      
            {
                fast = head;
                while (fast != slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

[1]https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[2]https://leetcode-cn.com/problems/middle-of-the-linked-list/
[3]https://leetcode-cn.com/problems/linked-list-cycle-ii/