Given a circular linked list, implement an algorithm which returns node at the begin- ning 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 [the same C as earlier] output: C

__author__ = 'nitin'

class Node:
    def __init__(self,initdata):
        self.data=initdata
        self.next=None
    def getData(self):
        return self.data
    def setData(self,item):
        self.data=item
    def getNext(self):
        return self.next
    def setNext(self,item):
        self.next=item

def find_circular_node(n0):
    n1=n0
    n2=n0
    while n2.getNext() is not None:
        n1=n1.getNext()
        n2=n2.getNext().getNext()
        if n1==n2:
            break
    if n2.getNext() is None:
        return None
    n1=n0
    while n1!=n2:
        n1=n1.getNext()
        n2=n2.getNext()
    return n2.getData()

n0=Node('A')
n1=Node('B')
n2=Node('C')
n3=Node('D')
n4=Node('E')
n0.setNext(n1)
n1.setNext(n2)
n2.setNext(n3)
n3.setNext(n4)
n4.setNext(n2)

print find_circular_node(n0)

Reverse every k element in linked list

__author__ = 'nitin'

class Node:
  def __init__(self,val,nxt):
    self.val = val
    self.nxt = nxt

def prnt(n):
  nxt = n.nxt
  print n.val
  if(nxt is not None):
    prnt(nxt)

def k_reverse(n,k):
    current=n
    count=0
    last=None
    while(current is not None and count        nxt = current.nxt
        current.nxt = last
        last = current
        current = nxt
        count +=1
    if current is not None:
        n.nxt=k_reverse(current,k)
    return last

n0 = Node(9,None)
n1 = Node(8,n0)
n2 = Node(7,n1)
n3 = Node(6,n2)
n4 = Node(5,n3)
n5 = Node(4,n4)
n6 = Node(3,n5)
n7 = Node(2,n6)
n8 = Node(1,n7)


prnt(n8)
print "\n"
result = k_reverse(n8,4)
prnt(result)