{"id":459,"date":"2016-11-28T12:25:24","date_gmt":"2016-11-28T17:25:24","guid":{"rendered":"http:\/\/www.ferociouscoder.com\/blog\/?p=459"},"modified":"2016-11-28T12:25:24","modified_gmt":"2016-11-28T17:25:24","slug":"hackerrank-cracking-coding-interview-linked-lists-detect-cycle","status":"publish","type":"post","link":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html","title":{"rendered":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle"},"content":{"rendered":"<p>For this problem we can apply a classic algorithm known as the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Cycle_detection#Tortoise_and_hare\" target=\"_blank\">tortoise and hare algorithm<\/a> by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node in the LinkedList and we will know that a cycle has been detected.<\/p>\n<p>The wikipedia article I have linked also mentions some other algorithms for cycle detection that can be read for fun.<\/p>\n<p>Problem: <a href=\"https:\/\/www.hackerrank.com\/challenges\/ctci-linked-list-cycle\" target=\"_blank\">https:\/\/www.hackerrank.com\/challenges\/ctci-linked-list-cycle<\/a><\/p>\n<p>Solution:<\/p>\n<pre class=\"brush: java; title: ; notranslate\" title=\"\">\r\nboolean hasCycle(Node head) {\r\n    if (head == null || head.next == null) {\r\n        return false;\r\n    }\r\n    Node tortoise = head;\r\n    Node hare = head;\r\n    while (tortoise != null &amp;&amp; hare != null) {\r\n        tortoise = tortoise.next;\r\n        hare = hare.next;\r\n        if (hare != null) {\r\n            hare = hare.next;\r\n            if (tortoise == hare) {\r\n                return true;\r\n            }\r\n        }\r\n    }\r\n    return false;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>For this problem we can apply a classic algorithm known as the tortoise and hare algorithm by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node &hellip; <a href=\"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[14,28,29,19],"tags":[33,32,20,40],"class_list":["post-459","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-cracking-the-coding-interview","category-hackerrank","category-java","tag-ctci","tag-hackerrank","tag-java-2","tag-tortoise-and-hare"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder\" \/>\n<meta property=\"og:description\" content=\"For this problem we can apply a classic algorithm known as the tortoise and hare algorithm by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node &hellip; Continue reading Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle &rarr;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\" \/>\n<meta property=\"og:site_name\" content=\"Ferocious Coder\" \/>\n<meta property=\"article:published_time\" content=\"2016-11-28T17:25:24+00:00\" \/>\n<meta name=\"author\" content=\"Rawrosaur\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Rawrosaur\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\"},\"author\":{\"name\":\"Rawrosaur\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"headline\":\"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle\",\"datePublished\":\"2016-11-28T17:25:24+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\"},\"wordCount\":154,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"keywords\":[\"ctci\",\"hackerrank\",\"java\",\"tortoise and hare\"],\"articleSection\":[\"Algorithms\",\"Cracking the Coding Interview\",\"HackerRank\",\"Java\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\",\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\",\"name\":\"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#website\"},\"datePublished\":\"2016-11-28T17:25:24+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/\",\"name\":\"Ferocious Coder\",\"description\":\"RAWR!\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\",\"name\":\"Rawrosaur\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"caption\":\"Rawrosaur\"},\"logo\":{\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\"},\"sameAs\":[\"http:\\\/\\\/www.ferociouscoder.com\\\/\"],\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/author\\\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html","og_locale":"en_US","og_type":"article","og_title":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder","og_description":"For this problem we can apply a classic algorithm known as the tortoise and hare algorithm by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node &hellip; Continue reading Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle &rarr;","og_url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html","og_site_name":"Ferocious Coder","article_published_time":"2016-11-28T17:25:24+00:00","author":"Rawrosaur","twitter_misc":{"Written by":"Rawrosaur","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#article","isPartOf":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html"},"author":{"name":"Rawrosaur","@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"headline":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle","datePublished":"2016-11-28T17:25:24+00:00","mainEntityOfPage":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html"},"wordCount":154,"commentCount":0,"publisher":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"keywords":["ctci","hackerrank","java","tortoise and hare"],"articleSection":["Algorithms","Cracking the Coding Interview","HackerRank","Java"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html","url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html","name":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle - Ferocious Coder","isPartOf":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#website"},"datePublished":"2016-11-28T17:25:24+00:00","breadcrumb":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-linked-lists-detect-cycle-459.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.ferociouscoder.com\/blog"},{"@type":"ListItem","position":2,"name":"Hackerrank: Cracking the Coding Interview \u2013 Linked Lists: Detect a Cycle"}]},{"@type":"WebSite","@id":"https:\/\/www.ferociouscoder.com\/blog\/#website","url":"https:\/\/www.ferociouscoder.com\/blog\/","name":"Ferocious Coder","description":"RAWR!","publisher":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.ferociouscoder.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a","name":"Rawrosaur","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","url":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","caption":"Rawrosaur"},"logo":{"@id":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg"},"sameAs":["http:\/\/www.ferociouscoder.com\/"],"url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/author\/admin"}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1mYMV-7p","jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/459","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/comments?post=459"}],"version-history":[{"count":1,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/459\/revisions"}],"predecessor-version":[{"id":460,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/459\/revisions\/460"}],"wp:attachment":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/media?parent=459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/categories?post=459"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/tags?post=459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}