# Python program to reverse a linked list
# Time Complexity : O(n)
# Space Complexity : O(n) as 'next'
#variable is getting created in each loop.

# Node class


class Node:

	# Constructor to initialize the node object
	def __init__(self, data):
		self.data = data
		self.next = None


class LinkedList:

	# Function to initialize head
	def __init__(self):
		self.head = None

	# Function to reverse the linked list
	def reverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next = current.next
			current.next = prev
			prev = current
			current = next
		self.head = prev

	# Function to insert a new node at the beginning
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# Utility function to print the linked LinkedList
	def printList(self):
		temp = self.head
		while(temp):
			print temp.data,
			temp = temp.next


# Driver program to test above functions
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)

print "Given Linked List"
llist.printList()
llist.reverse()
print "\nReversed Linked List"
llist.printList()

from collections import Counter

def find_parity_outliers(nums):
  return [
    x for x in nums
    if x % 2 != Counter([n % 2 for n in nums]).most_common()[0][0]
  ]

find_parity_outliers([1, 2, 3, 4, 6]) # [1, 3]

my_list = [1, 2, 3, 4, 5]
removed_element = my_list.pop(2)  # Remove and return element at index 2
print(removed_element)  # 3
print(my_list)  # [1, 2, 4, 5]

last_element = my_list.pop()  # Remove and return the last element
print(last_element)  # 5
print(my_list)  # [1, 2, 4]

class Rectangle:
    pass

class Square(Rectangle):
    pass

rectangle = Rectangle()
square = Square()

print(isinstance(rectangle, Rectangle))  # True
print(isinstance(square, Rectangle))     # True
print(isinstance(square, Square))        # True
print(isinstance(rectangle, Square))     # False

def print_x_pattern(size):
    i,j = 0,size - 1

    while j >= 0 and i < size:

        initial_spaces = ' '*min(i,j)
        middle_spaces = ' '*(abs(i - j) - 1)
        final_spaces = ' '*(size - 1 - max(i,j))

        if j == i:
            print(initial_spaces + '*' + final_spaces)
        else:
            print(initial_spaces + '*' + middle_spaces + '*' + final_spaces)

        i += 1
        j -= 1

print_x_pattern(7)