链表中倒数第K个结点

曾经终败给现在 2023-06-05 05:48 124阅读 0赞

题目描述： 输入一个链表，输出该链表中倒数第k个结点。假设此链表中有6个结点，各结点的值分别是1、2、3、4、5、6。我们想要获取倒数第3个结点，即值为4。

思路：最易想到的解法是先走到链表的尾端，再从尾端回溯k步，即得到倒数第k个结点。但是单向链表的结点只有从前往后的指针，没有从后往前的指针。但是，如果我们从前往后遍历链表直到尾端呢？假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n-k+1个结点。但是要获取到链表的结点个数n就要遍历链表，得到n之后再从头结点开始往后走n-k+1步即可。但是此方法需要遍历链表两次，第一次统计出链表的个数，第二次就能找到倒数第k个结点。最好的方法仅需遍历链表一次，思想如下：定义两个指针，第一个指针从链表的头指针开始遍历向后走k-1步，第二个指针保持不动；接下来，从第k步开始，两个指针同时向后移动，每次步长为一。由于两个指针的距离始终保持在k-1上，当第一个指针到达链表的尾部时，第二个指针正好到达倒数第k个结点。

代码如下：

#include <iostream>
    using namespace std;
    typedef struct ListNode
    {
        int data;
        ListNode* next;
        ListNode(int x) :data(x), next(NULL)
        {}
    }link;
    
    //打印链表
    void ShowList(link* head)
    {
        link* temp = head;
        while (temp)
        {
    	cout << temp->data << " ";
    	temp = temp->next;
        }
        cout << endl;
    }
    
    //找到链表倒数第K个结点
    link* FindKthToTail(link* head, unsigned int k)
    {
        if (head == NULL || k == 0)
        {
    	return NULL;
        }
        //定义俩指针
        link* p_Fast = head;
        link* p_Slow = head;
        for (unsigned int i = 0; i < k - 1; ++i)
        {
    	if (p_Fast->next != NULL)
    	{
    	    p_Fast = p_Fast->next;
    	}
    	else
    	{
    	    return NULL;
    	}
        }
        while (p_Fast->next != NULL)
        {
    	p_Fast = p_Fast->next;
    	p_Slow = p_Slow->next;
        }
        return p_Slow;
    }
    
    int main()
    {
        link head(1);
        link n1(2);
        link n2(3);
        link n3(4);
        link n4(5);
        link n5(6);
        head.next = &n1;
        n1.next = &n2;
        n2.next = &n3;
        n3.next = &n4;
        n4.next = &n5;
        ShowList(&head);
        unsigned int k = 3;
        link* temp = NULL;
        temp = FindKthToTail(&head, k);
        cout << temp->data << endl;
        return 0;
    }

![20191008145257253.png][]

[20191008145257253.png]: /images/20230601/1a51b8ec0de44613bb118e2f5cbb6162.png