Search This Blog

Friday, March 21, 2014

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)

You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

__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 add_numbers(n1,n2,carry):
    if n1 is None:
        return None
    while n1.getData() is not None:
        res_num=n1.getData() + n2.getData() + carry
        if res_num>10:
            carry=res_num % 10
            new_num=res_num - carry
            result_node=Node(new_num)
        elif res_num==10:
            carry=1
            new_num=0
            result_node=Node(new_num)
        else:
            result_node=Node(res_num)
        next_node=add_numbers(n1.getNext(), n2.getNext(),carry)
        result_node.setNext(next_node)
        return result_node

def print_list(result):
    current=result
    nxt = current.getNext()
    print current.getData()
    if(nxt is not None):
        print_list(nxt)

n0=Node(3)
n1=Node(1)
n2=Node(5)
n0.setNext(n1)
n1.setNext(n2)

n3=Node(5)
n4=Node(9)
n5=Node(2)
n3.setNext(n4)
n4.setNext(n5)

print_list(n0)
print ""
print_list(n3)
print ""
final_result=add_numbers(n0,n3,0)
print_list(final_result)

My Profile

My photo
can be reached at 09916017317