每日一题:环形链表Ⅱ(LeetCode 142)

题目

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

示例:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

解答

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //首先判断链表是否有环:定义fast和slow两个指针,fast一次走2步,slow一次走1步
        //当fast与slow相遇时,则代表有环
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast != NULL && fast->next != NULL)
        {
            fast  = fast->next->next;
            slow = slow->next;

            //fast与slow相遇,有环
            if(fast == slow)
            {
                //定义a,b两个指针,a指向链表头结点,b指向fast与slow相遇的结点
                //a,b分别每次走一步,相遇时,就是入环所在位置
                ListNode *a = head;
                ListNode *b = fast;

                while(a != b)
                {
                    a = a->next;
                    b = b->next;
                }
                //有环,返还入口结点
                return a;
            }

        }
        // 无环
        return NULL;
    }
};
THE END
分享
二维码
打赏
海报
每日一题:环形链表Ⅱ(LeetCode 142)
题目 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 示例: 输入:head = [3,2,0,-4], pos = 1 输……
<<上一篇
下一篇>>