出力チェーンテーブル逆数K番目のノード

タイトルの説明:
一方向チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
分析:
方法1:チェーンテーブルの最後からK番目のノードを出力するには、まずチェーンテーブルの長さNを求め、チェーンテーブル出力チェーンテーブルのN-K+1番目のノードを最初から遍歴すればよいというのが最も自然な考え方である.注意本題の数字は1から数えます.つまり、最後から1番目のノードがチェーンテーブルの最後のノードです.例えばチェーンテーブルの長さが4で、最後から2番目のノードを出力する必要がある場合は、チェーンテーブルの3番目のノードを最初から出力するだけでよい.この構想コードは以下の通りである.

struct node {
 int data;
 struct node* next;
};

struct node *getK1(struct node *list, int k)
{
    int n = length(list);  //      
    if (k > n) return NULL;
    struct node *current = list;
    int i = 0;
    for (; i<n-k; i++)  //    ，   N-K+1   
        current = current->next;
    return current;
}

int length(struct node *head)
{
 struct node *current = head;
 int count = 0;
 while (current != NULL) {
 count++;
 current = current->next;
 }
 return count;
}

方法2:方法1チェーンテーブルを2回遍歴し,1回目に長さを求め,2回目に結点を求める.もう一つの巧みな方法は、チェーンテーブルの長さを求めず、チェーンテーブルを一度遍歴すればよいということです.方法は、2つのポインタp 1,p 2を設定し、まずp 1とp 2がheadを指し、次いでp 2がkステップ前進し、p 1とp 2の間にk個のノードが間隔を置いている.最後にp 1とp 2は同時に前方に移動し,p 2がチェーンテーブルの末尾に達するとp 1はちょうど逆数K番目のノードを指す.メソッド・コードは次のとおりです.

struct node *getK(struct node *head, int k)
{
    struct node *p1, *p2;
    p1 = p2 = head; //      
    for (; k>0 && p2!=NULL; k--)
        p2 = p2->next; //p2  k 
    if (k > 0) return NULL; //        ，  NULL
    while (p2 != NULL) { //  p1 p2    
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}