Determine if a linked list is circular.
The idea here is to move a slow pointer and a fast pointer and if there is a circle, the pointers eventually meet at the same node.
At each step, slow pointer s moves one node and fast pointer f moves two nodes. If s enters a circle, f will be j nodes ahead of s. Since it’s a circle, it also means that f is k – j nodes behind s, where k is number of nodes in the circle. Because s moves forward one node at a time and f moves forward two nodes at a time, f gets one node closer to s at each step.
Since it takes at most k steps for f to meet with s at the same node, and k <= n where n is number of nodes, the runtime is O(n).<\/p>\n\n\n\n
bool isCircular(Node head) {\n Node s = head\n Node f = head\n\n while (true) {\n if (s.next)\n s = s.next\n else\n return false\n\n if (f.next && f.next.next)\n f = f.next.next\n else\n return false\n\n if (f == s)\n return true\n }\n return false\n}<\/pre>\n\n\n\nHere’s a bit of a math explanation for the circle.
k = number of nodes in circle
i = number of steps taken after s has entered circle
j = number of nodes f is ahead of s after s has entered circle
fp = position of fast pointer in circle
sp = position of slow pointer in circle<\/p>\n\n\n\n
Here is the position sp and fp, at any step i
sp = i % k
fp = (2 * i + j) % k
And where sp = fp is where the two pointers meet, or
i % k = (2 * i + j) % k
Let’s do an example. For a circle of length k = 100 and a fast pointer j = 12 nodes ahead, find i where fp = sp.
When i is 0, the slow pointer is at 0 and the fast pointer is 12 nodes ahead just as we would expect.<\/p>\n\n\n\n
\n\n0 % 100
(2 * 0 + 12) % 100<\/p>\n<\/div>\n\n\n\n
\n0 = sp
12 = fp<\/p>\n<\/div>\n\n\n\n
\n<\/p>\n<\/div>\n\n\n\n
<\/div>\n<\/div>\n\n\n\nAnd when i = 88 steps taken, the two pointers meet. This can be simplified to k – j = 88.<\/p>\n\n\n\n
\n\n88 % 100
(2 * 88 + 12) % 100<\/p>\n<\/div>\n\n\n\n
\n88 = sp
88 = fp<\/p>\n<\/div>\n\n\n\n
\n<\/p>\n<\/div>\n\n\n\n
<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"Determine if a linked list is circular. The idea here is to move a slow pointer and a fast pointer and if there is a circle, the pointers eventually meet at the same node. At each step, slow pointer s moves one node and fast pointer f moves two nodes. If s enters a circle, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2,"menu_order":19,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/126"}],"collection":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=126"}],"version-history":[{"count":63,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/126\/revisions"}],"predecessor-version":[{"id":692,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/126\/revisions\/692"}],"up":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/2"}],"wp:attachment":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=126"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}