链表中倒数第k个节点详解编程语言

题目：输入一个链表，输出该链表中倒数第k个节点。本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值一次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点，链表节点定义如下：

typedef int DataType; 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode;

【方案】
方案一：
先遍历整个链表，再往回走k步，就可得到链表倒数的第k个节点。但是，单链表没有往回走的指针。

方案二：
先遍历整个链表得到n个节点，再从走n-k+1步就能得到链表倒数的第k个节点。但是，这需要遍历两遍链表。

方案三：
先定义两个指针，即前指针和后指针。首先，前指针先行k-1步，后指针不动；然后，到k步时两个指针同时走。当前指针到达链尾时，后指针就到了链表倒数的第k个节点。可见：这只需要遍历一遍链表，可行！

【解题思路】
1、让前指针从头节点开始向前走两步（2=3-1，即k-1）到达第三个节点，如下图A。
2、把后指针初始化指向链表的头节点，如下图B。
3、让两个指针同时向前遍历。当前指针到达链表的尾节点时，后节点指向的就是链表倒数的第k个节点，如下图C。
如图所示：

图1 前后两指针变化过程图

【代码】
代码1：

Node* FindKTailList(pList plist, unsigned int k) 
{ 
    pNode pHead = plist; 
    pNode pBehind = NULL; 
 
    for (unsigned int i = 0; i < k - 1; ++i) 
    { 
        pHead = pHead->next; 
    } 
    pBehind = plist; 
    while (pHead->next != NULL) 
    { 
        pHead = pHead->next; 
        pBehind = pBehind->next; 
    } 
    return pBehind; 
}

注意：上述代码存在三个潜在风险
1、当输入的plist为空指针时，将会造成程序崩溃。
2、当节点数小于k值时，也会造成程序崩溃。
3、当k值为0时，仍然会造成程序崩溃。

解决风险的方法：
1、当输入链表的头指针为空时，返回空。
2、在for循环里加if语句判断，可避免风险。
3、当k值为0时，无实际意义，应返回空指针。

代码2：（优化）

Node* FindKTailList(pList plist, unsigned int k) 
{ 
    if (plist == NULL || k == 0) 
    { 
        return NULL; 
    } 
 
    pNode pahead = plist; 
    pNode pbehind = NULL; 
 
    for (unsigned int i = 0; i < k - 1; ++i) 
    { 
        if (pahead->next != NULL) 
        { 
            pahead = pahead->next; 
        } 
        else 
        { 
            return NULL; 
        }    
    } 
    pbehind = plist; 
 
    while (pahead->next != NULL) 
    { 
        pahead = pahead->next; 
        pbehind = pbehind->next; 
    } 
    return pbehind; 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
    assert(pplist); 
    *pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
    pNode cur = *pplist; 
    pNode pnode = NULL; 
    assert(pplist); 
    pnode = (pNode)malloc(sizeof(Node)); 
    if (pnode == NULL) 
    { 
        perror("PushBack::malloc"); 
        exit(EXIT_FAILURE); 
    } 
    pnode->data = x; 
    pnode->next = NULL; 
    if (cur == NULL) 
    { 
        *pplist = pnode; 
    } 
    else 
    { 
        while (cur->next != NULL) 
        { 
            cur = cur->next; 
        } 
        cur->next = pnode; 
    } 
} 
 
void Display(pList plist) 
{ 
    pNode cur = plist; 
    while (cur) 
    { 
        printf("%d-->", cur->data); 
        cur = cur->next; 
    } 
    printf("over/n"); 
} 
 
void PrintNode(pList plist) 
{ 
    pNode cur = plist; 
    printf("%d/n", cur->data); 
} 
 
void Destroy(pList *pplist) 
{ 
    pNode cur = *pplist; 
    assert(pplist); 
    while (cur) 
    { 
        pNode del = cur; 
        cur = cur->next; 
        free(del); 
    } 
    *pplist = NULL; 
} 
 
Node* FindKTailList(pList plist, unsigned int k) 
{ 
    if (plist == NULL || k == 0) 
    { 
        return NULL; 
    } 
 
    pNode pahead = plist; 
    pNode pbehind = NULL; 
 
    for (unsigned int i = 0; i < k - 1; ++i) 
    { 
        if (pahead->next != NULL) 
        { 
            pahead = pahead->next; 
        } 
        else 
        { 
            return NULL; 
        }    
    } 
    pbehind = plist; 
 
    while (pahead->next != NULL) 
    { 
        pahead = pahead->next; 
        pbehind = pbehind->next; 
    } 
    return pbehind; 
} 
 
 
void test1() 
{ 
    pList plist; 
    pNode ret = NULL; 
    InitLinkList(&plist); 
    PushBack(&plist, 1); 
    PushBack(&plist, 2); 
    PushBack(&plist, 3); 
    PushBack(&plist, 4); 
    PushBack(&plist, 5); 
    PushBack(&plist, 6); 
    ret = FindKTailList(plist, 6); 
    Display(plist); 
    PrintNode(ret); 
    Destroy(&plist); 
} 
 
int main() 
{ 
    test1(); 
    system("pause"); 
    return 0; 
}

运行结果为：

测试用例：
1、功能测试：第k个节点在链表的中间，是头节点，是尾节点。
2、特殊输入测试：链表头节点为空指针，节点数少于k，k=0。

举一反三：
难于解决的链表题可尝试用两个指针，一个走快，一个走慢。

【附加】

pNode FindKNode(pList plist, int k) 
{ 
    pNode fast = plist; 
    pNode slow = plist; 
    while (fast && fast->next) 
    { 
        if (--k <= 0)//k-1次后，slow再走  
        { 
            slow = slow->next; 
        } 
        fast = fast->next; 
    } 
    if (k <= 0)//执行完while后才能输出  
    { 
        return slow; 
    } 
    return NULL; 
}