查找单链表倒数第k个结点(***

要查找单链表倒数第k个结点，可以采用双指针的方法。

具体操作如下：

1. 定义两个指针p1和p2，初始都指向头结点。

2. 让p1指针先移动k个结点。

3. 然后同时移动p1和p2指针，直到p1指针到达链表末尾。

4. 此时p2指针所指的结点就是倒数第k个结点。

代码如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
{
    if(pListHead == NULL || k == 0)
        return NULL;
 
    ListNode* p1 = pListHead;
    ListNode* p2 = pListHead;
 
    // p1指针先移动k个结点
    for(unsigned int i=0; i<k-1; ++i)
    {
        if(p1->next != NULL)
            p1 = p1->next;
        else
            return NULL;    // 如果链表长度小于k，返回NULL
    }
 
    // p1和p2指针同时移动
    while(p1->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
 
    return p2;
}

相关问题

在带头结点的非空单链表中查找倒数第k个结点,如果查找不成功返回0,查找成功通过参

首先，需要先判断该带头结点的非空单链表是否为一条有效的链表，即除了头结点以外至少要有一个结点存在。如果没有任何有效数据表明该链表中没有任何结点，也就不可能找到倒数第k个结点，因此直接返回0。

接下来，可以定义两个指针，一个指针从头结点开始向前走k-1步，之后两个指针同时向前走，当前面的指针到达链表尾部时，后面的指针就指向了倒数第k个结点。如果前面的指针走到了链表尾部还没有走k-1步，说明链表长度小于k，无法找到倒数第k个结点，同样返回0。

最后，可以将找到的倒数第k个结点的指针通过参返回给调用者，状态为查找成功，如果无法找到则返回0并标记为查找失败。

编写函数查找带头结点单链表的倒数第四个元素

假设带头结点单链表的结构体如下：

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkedList;

则可以编写如下的函数来查找带头结点单链表的倒数第四个元素：

Node* findFourthFromEnd(LinkedList head) {
    Node *p = head;
    int count = 0;
    while (p->next != NULL) {
        count++;
        p = p->next;
    }
    if (count < 4) {
        return NULL;
    }
    p = head;
    for (int i = 0; i < count - 3; i++) {
        p = p->next;
    }
    return p;
}

该函数首先遍历整个带头结点单链表，统计链表节点数量，如果节点数量小于4，则无法找到倒数第四个元素，返回 NULL。否则，再次遍历链表，找到倒数第四个元素并返回。