Showing posts with label List. Show all posts
Showing posts with label List. Show all posts

Sorted Linked List to Balanced Binary search tree

class LNode :

def __init__(self):

self.data = None

self.next = None

class TNode :

def __init__(self):

self.data = None

self.left = None

self.right = None

head = None

def sortedListToBST():

global head

n = countLNodes(head)

return sortedListToBSTRecur(n)

def sortedListToBSTRecur( n) :

global head

if (n <= 0) :

return None

left = sortedListToBSTRecur( int(n/2))

root = newNode((head).data)

root.left = left

head = (head).next

root.right = sortedListToBSTRecur( n - int(n/2) - 1)

return root

def countLNodes(head) :

count = 0

temp = head

while(temp != None):

temp = temp.next

count = count + 1

return count

def push(head, new_data) :

new_node = LNode()

new_node.data = new_data

new_node.next = (head)

(head) = new_node

return head

def printList(node):

while(node != None):

print( node.data ,end= " ")

node = node.next

def newNode(data) :

node = TNode()

node.data = data

node.left = None

node.right = None

return node

def preOrder( node) :

if (node == None) :

return

print(node.data, end = " " )

preOrder(node.left)

preOrder(node.right)

head = None

head = push(head, 7)

head = push(head, 6)

head = push(head, 5)

head = push(head, 4)

head = push(head, 3)

head = push(head, 2)

head = push(head, 1)

print("Given Linked List " )

printList(head)

root = sortedListToBST()

print("\nPreOrder Traversal of constructed BST ")

preOrder(root)

Find size of Doubly Linked List

class Nodes:

def __init__(self):

self.data = None

self.next = None

self.prev = None

def push( ref, new_data):

new_node = Nodes()

new_node.data = new_data

new_node.next = (ref)

new_node.prev = None

if ((ref) != None):

(ref).prev = new_node

(ref) = new_node

return ref

def findSize(node):

res = 0

while (node != None):

res = res + 1

node = node.next

return res

head = None

head = push(head, 4)

head = push(head, 3)

head = push(head, 2)

head = push(head, 1)

print(findSize(head))


Split a Circular Linked List into two halves

class Node:

def __init__(self, data):

self.data = data

self.next = None

class CircularLinkedList:

def __init__(self):

self.head = None

def push(self, data):

ptr1 = Node(data)

temp = self.head

ptr1.next = self.head

if self.head is not None:

while(temp.next != self.head):

temp = temp.next

temp.next = ptr1

else:

ptr1.next = ptr1 

self.head = ptr1

def printList(self):

temp = self.head

if self.head is not None:

while(True):

print ("%d" %(temp.data),end=' ')

temp = temp.next

if (temp == self.head):

break

def splitList(self, head1, head2):

slow_ptr = self.head

fast_ptr = self.head

if self.head is None:

return

while(fast_ptr.next != self.head and

fast_ptr.next.next != self.head ):

fast_ptr = fast_ptr.next.next

slow_ptr = slow_ptr.next

if fast_ptr.next.next == self.head:

fast_ptr = fast_ptr.next

head1.head = self.head

if self.head.next != self.head:

head2.head = slow_ptr.next

fast_ptr.next = slow_ptr.next

slow_ptr.next = self.head

head = CircularLinkedList()

head1 = CircularLinkedList()

head2 = CircularLinkedList()

head.push(12)

head.push(56)

head.push(2)

head.push(11)

print ("Original Circular Linked List")

head.printList()

head.splitList(head1 , head2)

print ("\nFirst Circular Linked List")

head1.printList()

print ("\nSecond Circular Linked List")

head2.printList()


Replace multiple words

test_str = 'Python for engineers,The complete solution for python programs'

print("The original string is : " + str(test_str))

word_list = ["for", 'The', 'solution']

repl_wrd = 'hai'

res = ' '.join([repl_wrd if idx in word_list else idx for idx in test_str.split()])

print("String after multiple replace : " + str(res))


Check if the characters in a string form a Palindrome in O(1) extra space

def firstPos(str, start, end):

firstChar = -1

for i in range(start, end + 1):

if (str[i] >= 'a' and str[i] <= 'z') :

firstChar = i

break

return firstChar

def lastPos(str, start, end):

lastChar = -1

for i in range(start, end - 1, -1) :

if (str[i] >= 'a' and str[i] <= 'z') :

lastChar = i

break

return lastChar

def isPalindrome(str):

firstChar = 0

lastChar = len(str) - 1

ch = True

for i in range(len(str)) :

firstChar = firstPos(str, firstChar, lastChar);

lastChar = lastPos(str, lastChar, firstChar);

if (lastChar < 0 or firstChar < 0):

break

if (str[firstChar] == str[lastChar]):

firstChar += 1

lastChar -= 1

continue

ch = False

break

return (ch)

if __name__ == "__main__":


str = "m a 343 la y a l am"

if (isPalindrome(str)):

print("YES")

else:

print("NO")

 

program to count Even and Odd numbers in a List Using Python Lambda Expressions

list1 = [10, 21, 4, 45, 66, 93, 11]

odd_count = len(list(filter(lambda x: (x%2 != 0) , list1)))

even_count = len(list(filter(lambda x: (x%2 == 0) , list1)))

print("Even numbers in the list: ", even_count)

print("Odd numbers in the list: ", odd_count)


Break a list into chunks of size N

my_list = ['python', 'for', 'engineers', 'like',

'complete','solution', 'for', 'python',

'related','queries']

def divide_chunks(l, n):

for i in range(0, len(l), n):

yield l[i:i + n]

n = 5

x = list(divide_chunks(my_list, n))

print (x)


Printing anagrams together using List and Dictionary

def allAnagram(input):

dict = {}

for strVal in input:

key = ''.join(sorted(strVal))

if key in dict.keys():

dict[key].append(strVal)

else:

dict[key] = []

dict[key].append(strVal)

output = ""

for key,value in dict.items():

output = output + ' '.join(value) + ' '

return output

if __name__ == "__main__":

input=['cat', 'dog', 'tac', 'god', 'act']

print (allAnagram(input))


program to rotate doubly linked list by N nodes

class Node:    

    def __init__(self,data):    

        self.data = data;    

        self.previous = None;    

        self.next = None;    

class RotateList:    

    def __init__(self):    

        self.head = None;    

        self.tail = None;    

        self.size = 0;    

    def addNode(self, data):    

        newNode = Node(data);    

        if(self.head == None):    

            self.head = self.tail = newNode;    

            self.head.previous = None;    

            self.tail.next = None;    

        else:    

            self.tail.next = newNode;    

            newNode.previous = self.tail;    

            self.tail = newNode;    

            self.tail.next = None;    

        self.size = self.size + 1;    

    def rotateList(self, n):    

        current = self.head;    

        if(n == 0 or n >= self.size):    

            return;    

        else:   

            for i in range(1, n):    

                current = current.next;                  

            self.tail.next = self.head;    

            self.head = current.next;    

            self.head.previous = None;    

            self.tail = current;    

            self.tail.next = None;              

    def display(self):    

        current = self.head;    

        if(self.head == None):    

            print("List is empty");    

            return;                  

        while(current != None):    

            print(current.data),    

            current = current.next;    

        print();    

dList = RotateList();    

dList.addNode(1);    

dList.addNode(2);    

dList.addNode(3);    

dList.addNode(4);    

dList.addNode(5);    

print("Original List: ");    

dList.display();    

dList.rotateList(3);    

print("Updated List: ");    

dList.display();   


program to create a doubly linked list from a ternary tree

class Node:    

    def __init__(self,data):    

        self.data = data;    

        self.left = None;    

        self.middle = None;    

        self.right = None;    

class TernaryTreeToDLL:    

    def __init__(self):    

        self.root = None;    

        self.head = None;    

        self.tail = None;    

    def convertTernaryToDLL(self, node):    

        if(node == None):    

            return;    

        left = node.left;    

        middle = node.middle;    

        right = node.right;    

        if(self.head == None):    

            self.head = self.tail = node;    

            node.middle = None;    

            self.head.left = None;    

            self.tail.right = None;    

        else:    

            self.tail.right = node;    

            node.left = self.tail;    

            node.middle = None;    

            self.tail = node;    

            self.tail.right = None;    

        self.convertTernaryToDLL(left);    

        self.convertTernaryToDLL(middle);    

        self.convertTernaryToDLL(right);        

    def displayDLL(self):    

        current = self.head;    

        if(self.head == None):    

            print("List is empty");    

            return;    

        print("Nodes of generated doubly linked list: ");    

        while(current != None):    

            print(current.data),    

            current = current.right;    

tree = TernaryTreeToDLL();    

tree.root = Node(5);    

tree.root.left = Node(10);    

tree.root.middle = Node(12);    

tree.root.right = Node(15);    

tree.root.left.left = Node(20);    

tree.root.left.middle = Node(40);    

tree.root.left.right = Node(50);    

tree.root.middle.left = Node(24);    

tree.root.middle.middle = Node(36);    

tree.root.middle.right = Node(48);    

tree.root.right.left = Node(30);    

tree.root.right.middle = Node(45);    

tree.root.right.right = Node(60);    


tree.convertTernaryToDLL(tree.root);    

     

tree.displayDLL();

program to create and display a doubly linked list

class Node:    

    def __init__(self,data):    

        self.data = data;    

        self.previous = None;    

        self.next = None;                

class DoublyLinkedList:    

    def __init__(self):    

        self.head = None;    

        self.tail = None;                

    def addNode(self, data):    

        newNode = Node(data);                

        if(self.head == None):    

            self.head = self.tail = newNode;    

            self.head.previous = None;    

            self.tail.next = None;    

        else:    

            self.tail.next = newNode;    

            newNode.previous = self.tail;    

            self.tail = newNode;    

            self.tail.next = None;                   

    def display(self):    

        current = self.head;    

        if(self.head == None):    

            print("List is empty");    

            return;    

        print("Nodes of doubly linked list: ");    

        while(current != None):     

            print(current.data),;    

            current = current.next;                   

dList = DoublyLinkedList();    

dList.addNode(1);    

dList.addNode(2);    

dList.addNode(3);    

dList.addNode(4);    

dList.addNode(5);    

dList.display();  

Program to find the maximum and minimum value node from a circular linked list

class Node:    

    def __init__(self,data):    

        self.data = data;    

        self.next = None;    

class CreateList:    

    def __init__(self):    

        self.head = Node(None);    

        self.tail = Node(None);    

        self.head.next = self.tail;    

        self.tail.next = self.head;      

    def add(self,data):    

        newNode = Node(data);    

        if self.head.data is None:    

            self.head = newNode;    

            self.tail = newNode;    

            newNode.next = self.head;    

        else:    

            self.tail.next = newNode;    

            self.tail = newNode;    

            self.tail.next = self.head;                 

    def minNode(self):    

        current = self.head;    

        minimum = self.head.data;    

        if(self.head == None):    

            print("List is empty");    

        else:    

            while(True):       

                if(minimum > current.data):    

                    minimum = current.data;    

                current= current.next;    

                if(current == self.head):    

                    break;    

        print("Minimum value node in the list: "+ str(minimum));    

    def maxNode(self):    

        current = self.head;    

        maximum = self.head.data;    

        if(self.head == None):    

            print("List is empty");    

        else:    

            while(True):       

                if(maximum < current.data):    

                    maximum = current.data;    

                current= current.next;    

                if(current == self.head):    

                    break;    

        print("Maximum value node in the list: "+ str(maximum));    

class CircularLinkedList:    

    cl = CreateList();    

    cl.add(5);    

    cl.add(20);    

    cl.add(10);    

    cl.add(1);    

    cl.minNode();    

    cl.maxNode();    


Transpose of a matrix (nested list) in python

row1 = [13,25,73]
row2 = [54,95,36]
row3 = [27,98,19]

matrix = [row1, row2, row3]
trmatrix = [[row[0] for row in matrix],[row[1] for row in matrix],  [row[2] for row in matrix]]
print'Transpose of a matrix',trmatrix

source: http://stackoverflow.com

Sorting the numbers in the List

L=int(raw_input("Enter the length of list: "))
p=list()
for i in range(L):
      num=int(raw_input("Enter the elements : "))
      p.append(num)
print '\nUnsorted list is: ',p
for i in range (len(p)):
 for j in range (i+1,len(p)):
  if p[i]>p[j]:
   t=p[i]
   p[i]=p[j]
   p[j]=t
else:
 print '\nSorted List is:' ,p

Search the Element in a list

flag=0
L=int(raw_input("Enter the length of list: "))
p=list()
for i in range(L):
      num=int(raw_input("Enter the elements : "))
      p.append(num)
j=int(raw_input("Enter the element to find: "))
     
for i in range(L):
      if (p[i]==j):
            flag=1
if flag==1:
      print "Element is found"
else:
        print "Element is not found"

Delete Duplicate numbers in a list

l1=list()
l2=list()
w=int(raw_input("Enter the elements in list:"))
for i in range(w):
      n=int(raw_input("Enter the list:"))
      l1.append(n)

for i in l1:
 if i not in l2:
  l2.append(i)
print ' Delete Duplicate numbers in a list: ', l2

Basic operations in Python List

l=[]
n=int(raw_input('Enter the no of elements added to list:'))
for i in range(n):
      element=int(raw_input('Enter the elements:'))
      l.append(element)
print '\nNew List is ',
m=int(raw_input('\nEnter the no of elements added to list using insert:'))
for i in range(m):
      u=int(raw_input('Enter the index to be added'))
      u1=int(raw_input('Enter the element to be added'))
      l.insert(u,u1)
print '\nNew List after insert operation is:   ',l
ch=int(raw_input('\nPress 1 to pop the last element\nPress 2 to pop the element in a particular index\nEnter the choice: '))
if ch==1:
 l.pop()
 print '\nNew List after deletion is: ',l
elif ch==2:
 p=int(raw_input('Enter the element index to be deleted'))
 l.pop(p)
 print '\nNew List after deletion is: ',l
else:
  print '\nInvalid choice'
print ' \nList elements are sorted:  ',l

To add elements in list using insert

y=[]
n=int(raw_input('Enter the no of elements added to list:'))
index=0
for i in range(n):
      element=int(raw_input('Enter the elements:'))
      y.insert(index, element)
      index=index+1
print y

To add elements inside a list using append

l=[]
n=int(raw_input('Enter the no of elements added to list:'))
for i in range(n):
      element=int(raw_input('Enter the elements:'))
      l.append(element)
print l

To count the elements in a nested list with all elements are list

a=[[3, 4, 5,8, 8 ], [5, 6, 7], [7, 8, 9]]

def count(a):
 j=0
 n=0
 for b in a:
     j=len(b)
     n=n+j
 return n

t= count(a)
print "No elements in the nested list are:",t