【数据结构】单链表—链表中倒数第K个结点 — 快慢指针

前端之家收集整理的这篇文章主要介绍了【数据结构】单链表—链表中倒数第K个结点 — 快慢指针前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

输入一个链表,输出该链表中倒数第K个结点。注:链表的尾结点是倒数第一个结点。
思路一:
遍历一遍链表,求出链表的长度。
正数 = 长度 - 倒数 + 1
如图所示:

然后遍历正数的次数,便得到了倒数第K个结点。但是这种方法需要遍历链表两次。

思路二:
遍历一次可以用快慢指针解法,即定义两个指针,快指针和慢指针,求倒数第K个:结点快指针先走K-1步,然后快慢指针一起走当快指针走到结尾,慢指针所指向的就是所求结点。

代码如下:

template<class T>
struct ListNode
{
    T _value;
    ListNode<T>* _next;

    ListNode(const T& value)
        :_value(value),_next(NULL)
    {}
};

template<class T>
class List
{
public:
    List()
        :_head(NULL)
    {}
    bool PushBack();
   ListNode<T>* FindLastKNode(int K)//寻找链表中倒数第K个节点,快慢指针,快指针先走K-1步,然后一起走直到快指针走到结尾慢指针指向的便是倒数第K个节点
    {
        int len = Length();
        if(K<=0 || K>len)
        {
            cout<<"输入无效,重新输入"<<endl;
            return NULL;
        }
        ListNode<T>* fast = _head;
        ListNode<T>* slow = _head;

        while(fast!=NULL && K--)
        {
            fast = fast->_next;
        }
        while(fast != NULL)//如果条件是fast->_next!=NULL则最后一个节点便是倒数第0个。。。。
        {
            slow = slow->_next;
            fast = fast->_next;
        }
        return slow;
    }


private:
    ListNode<T>* _head;
};
原文链接:https://www.f2er.com/datastructure/382472.html

猜你在找的数据结构相关文章