链表-双指针妙用

2020-04-15  本文已影响0人  zhtttyi

1. 返回链表的中间节点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

分析:

快慢指针同时指向头节点,快指针走两步,慢指针走一步

如果长度为偶数,那么快指针为NULL的时候停止,长度为奇数,fast->next为NULL的时候停止

慢指针指向的位置就是中间节点了

按照这种思路,实现代码如下:

LinkNode *findMidNode(LinkNode *head)

{

LinkNode *fast = head;

LinkNode *slow = head;

while(NULL!= fast &&NULL!= fast->next )

{

fast = fast->next->next;

slow = slow->next;

}

returnslow;

}

2.链表的中间节点

输入一个单向链表,输出该链表中倒数第k个结点。为符合计数习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例子

如:一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

分析:

定义两个指针,指针移动一个快,一个慢(链表的长度l)

1.快慢指针同时指向头结点

2.首先快指针移动k-1步,先走到第k个节点

3.快慢指针同时移动,直到快指针指向末尾,这时,快慢指针都走了l-k,

4.慢指针指向的节点即为我们需要寻找的节点

参考代码实现如下:

LinkNode *FindKthToTail(LinkNode *head,unsignedintk)

{

    if(NULL == head || 0 == k)

        return head;

    LinkNode *pFast = head;

    LinkNode *pSlow = head;

    unsigned int i = 0;

    //快指针先移动

    while(i < k -1)

    {

        if(NULL != pFast)

        {

            pFast = pFast->next;

        }

        //k大于链表的长度

        else

        {

            return NULL;

        }

        i++;

    }

    //快慢指针一起移动

    while(NULL != pFast->next)

    {

        pSlow = pSlow->next;

        pFast = pFast->next;

    }

    return pSlow;

}

3.判断链表是否有环

如何判断一个单链表是否有环?若有环,如何找出环的入口节点。

按照快慢指针的思路,使用两个指针,一个指针每次走一步,另一个每次走两步,如果链表有环,那么它们终将相遇,而如果没有环,快的指针最后会指向NULL。

按照这种思路,我们的参考代码如下:

//0:无环,1:有环

int hasLoop(LinkNode *head)

{

    if(NULL == head)

        return 0;

        LinkNode *slow = head;

        LinkNode *fast = head->next;

        //当快指针到末尾时,无环,结束

        while (NULL != fast  && NULL != slow)

       {

            //快慢相遇,有环

            if (fast == slow)

                return 1;

                slow = slow->next; // 慢指针每次走一步

                fast = fast->next;

                if (fast != NULL)

                    fast = fast->next;

    }

    return 0;

}

上一篇 下一篇

猜你喜欢

热点阅读