Skip to content

Instantly share code, notes, and snippets.

@habina
Created June 28, 2014 09:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save habina/d8bbd5fbe1567502c676 to your computer and use it in GitHub Desktop.
Save habina/d8bbd5fbe1567502c676 to your computer and use it in GitHub Desktop.
"""
============================================================================
Question : 2.6
Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input:A ->B->C->D->E-> C[thesameCasearlier]
Output:C
Solution : Faster pointer moves two steps at a time,
slower pointer moves onw step at a time,
after their first time meet,
reset fater pointer back to head
return slower when they meet again
Time Complexity : O(n)
Space Complexity: O(1)
Gist Link : https://gist.github.com/habina/d8bbd5fbe1567502c676
============================================================================
"""
import random
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __int__(self):
return self.value
def print_linkedList(node):
while node:
if(node.value != None):
print(node.value)
node = node.next
print()
def circularLinkedList():
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
h = Node('H')
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
f.next = g
g.next = h
h.next = c
return a
circular = circularLinkedList()
fast = circular.next.next
slow = circular.next
while slow != fast:
fast = fast.next.next
slow = slow.next
fast = circular
while slow != fast:
fast = fast.next
slow = slow.next
print(slow.value)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment