单链表查找倒数第k个节点

2023-06-26,,

题目描述:单链表查找倒数第k个节点


分析:单链表是一个单向的链式结构,所以不可能从链表尾部向前找第k个结点,因此只能想办法从链表的头部开始找。

假设一个给定一个链表,长度为 6,现在查找倒数第 2 个结点:


给定两个指针, fast 和 slow 开始都让他们指向头结点

首先,让 fast 指针先走到正数第 k 个结点,也就是走 k-1 步,这里 k=2,所以先让 fast 走1步

这时让 slow 指针跟着 fast 指针一块走,直到 fast 指针走到最后一个节点注意:这里是最后一个节点,而不是空节点),此时 slow 指针所指向的节点就是我们要找的倒数第 k 个结点了

当然,这里只是大致的思想,具体的很多细节问题(比如: k值大于链表的长度,k = 0 的情况等等),需要自己处理。


主要代码如下:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
    {
        if(pListHead == NULL || k == 0) //一些异常情况
        {
            return NULL;
        }
        
        ListNode* fast = pListHead;
        ListNode* slow = pListHead;
        
        while(fast && --k)  //这里一定要先自减,因为两个指针开始都指向头结点
        {
            fast = fast->next;
        }
        
        if(fast == NULL)  //即没找到的情况
        {
            return NULL;
        }
        
        if(k == 0)
        {
            while(fast->next != NULL)
            {
                fast = fast->next;
            	slow = slow ->next;
            }
            
        }

        return slow;
    }

《单链表查找倒数第k个节点.doc》

下载本文的Word格式文档,以方便收藏与打印。