141. 环形链表

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

题目描述:给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

思路:快慢指针

使用双指针,一个指针每次移动一个节点,一个指针每次移动两个节点,如果存在环,那么这两个指针一定会相遇。

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *l1 = head, *l2 = head;
        while(l2 != NULL && l2->next != NULL)
        {         
            l1 = l1->next;
            l2 = l2->next->next;
            if (l1 == l2) return true;
        }
        return false;
    }
};

标签: 141. 环形链表 , LeetCode , acm , c++ , cpp , 每日一题 , 算法 ,

共有10条评论

  1. Everyone lloves what yyou guys tend tto be up too. This kind oof clever work aand reporting! Keeep up tthe terrific works guys I've acded yyou guuys to oour blogroll.

  2. Admiring thee tim andd energy yoou put nto your site and detailed information youu offer. It's good to come across a blog every once in a while tthat isn't tthe same oold rehashed information. Excellent read! I've bookmaqrked your site andd I'm adeding youyr RSS fees to my Google account.

  3. Hello! Someone inn my Facebook group shared this site wih uss so I cae to check iit out. I'm definnitely enjoyig thhe information. I'm bookmarking and will bee tweting this tto my followers! Outstanding bllog annd amazkng design.

  4. Ahaa, its nice dicussion regarding this post here at this webb site, I ave read all that, soo now me also commenting here.

  5. I paay a quick visit eachh dayy some wweb sites and boogs to read content, bbut this boog provides quality basedd posts.

  6. My partner and I stumbled ovver here froom a differeent web page annd thought I might as ell chedk thins out. I like wha I see so now i'm following you. Look forwad tto exploring yohr web pagte repeatedly.

  7. Helklo there, I discovered your weeb site bby way off Google whilst searching ffor a elated topic, your websitee ggot heere up, it looks great. I've bookmarked it in myy golgle bookmarks. Hi there, jusdt became alert too yyour weblog through Google, aand found that it is ttuly informative. I'm going tto watch out for brussels. I'll appreciate if you continue ths inn future. A llot of peolle mighht bee benefited ffrom yoiur writing. Cheers!

  8. There is certainly a lot too kno about this topic. I love all thhe points you've made.

  9. I visuted several wweb sites but tthe audio feagure forr audio soings curent at thks web siite is ttruly wonderful.

  10. You actually make itt seem so esy witth your presentation bbut I finnd thyis topic to bee reall something whicxh I think I would never understand. It seems too comnplex and extremely broad for me. I'm looking forward for your next post, I will ttry to get the hang of it!

添加新评论