Create a link list of size N according to the given input literals. Each integer input is accompanied by an indicator which can either be 0 or 1. If it is 0, insert the integer in the beginning of the link list. If it is 1, insert the integer at the end of the link list. 
Hint: When inserting at the end, make sure that you handle NULL explicitly. 
Example 1:
Input:
LinkedList: 9->0->5->1->6->1->2->0->5->0
Output: 5 2 9 5 6
Explanation:
Length of Link List = N = 5
9 0 indicated that 9 should be
inserted in the beginning. Modified
Link List = 9.
5 1 indicated that 5 should be
inserted in the end. Modified Link
List = 9,5.
6 1 indicated that 6 should be
inserted in the end. Modified Link
List = 9,5,6.
2 0 indicated that 2 should be
inserted in the beginning. Modified
Link List = 2,9,5,6.
5 0 indicated that 5 should be
inserted in the beginning. Modified
Link List = 5,2,9,5,6. 
Final linked list = 5, 2, 9, 5, 6.
Example 2:
Input:
LinkedList: 5->1->6->1->9->1
Output: 5 6 9
Your Task:
You only need to complete the functions insertAtBeginning() and insertAtEnd() that takes the head of link list and integer value of the data to be inserted as inputs and returns the head of the modified link list. 
Expected Time Complexity: O(1) for insertAtBeginning() and O(N) for insertAtEnd().
Expected Auxiliary Space: O(1) for both.
Constraints:
1 <= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: '''    
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
'''
class Solution:
    #Function to insert a node at the beginning of the linked list.
    def insertAtBegining(self,head,x):
        # code here 
    
    #Function to insert a node at the end of the linked list.
    def insertAtEnd(self,head,x):
        # code here 



Solutions:
class Solution:

	def insertAtBegining(self, head, x):
		if not head:
			return Node(x)
		temp = Node(x)
		temp.next = head
		return temp

	def insertAtEnd(self, head, x):
		if head is None:
			return Node(x)
		temp = head
		while temp.next:
			temp = temp.next
		temp.next = Node(x)
		return head


class Solution:

	def insertAtBegining(self, head, x):
		insertN = Node(x)
		insertN.next = head
		head = insertN
		return head

	def insertAtEnd(self, head, x):
		insertN = Node(x)
		temp = head
		if temp:
			while temp.next:
				temp = temp.next
			temp.next = insertN
			return head
		else:
			return insertN


class Solution:

	def insertAtBegining(self, head, x):
		x1 = Node(x)
		if head == None:
			return x1
		x1.next = head
		head = x1
		return head

	def insertAtEnd(self, head, x):
		y1 = Node(x)
		if head == None:
			return y1
		y = head
		while y.next is not None:
			y = y.next
		y.next = y1
		return head


class Solution:

	def insertAtBegining(self, head, x):
		if head is None:
			head = Node(x)
			return head
		else:
			newNode = Node(x)
			newNode.next = head
			head = newNode
			return head

	def insertAtEnd(self, head, x):
		if head is None:
			head = Node(x)
			return head
		else:
			last = head
			while last.next:
				last = last.next
			last.next = Node(x)
			return head


class Solution:

	def insertAtBegining(self, head, x):
		node = Node(x)
		if head is None:
			return node
		node.next = head
		return node

	def insertAtEnd(self, head, x):
		if head is None:
			return self.insertAtBegining(head, x)
		node = Node(x)
		if head.next is None:
			head.next = node
			return head
		currentNode = head
		while currentNode.next is not None:
			currentNode = currentNode.next
		currentNode.next = node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		newNode = Node(x)
		if head == None:
			return newNode
		newNode.next = head
		head = newNode
		return head

	def insertAtEnd(self, head, x):
		newNode = Node(x)
		if head == None:
			return newNode
		current = head
		while current.next != None:
			current = current.next
		current.next = newNode
		return head


class Solution:

	def insertAtBegining(self, head, x):
		curr = Node(x)
		if head is not None:
			curr.next = head
		head = curr
		return head

	def insertAtEnd(self, head, x):
		curr = Node(x)
		if head is None:
			return curr
		last = head
		while last.next:
			last = last.next
		last.next = curr
		return head


class Solution:

	def insertAtBegining(self, head, x):
		new_node = Node(x)
		new_node.next = head
		head = new_node
		return head

	def insertAtEnd(self, head, x):
		if not head:
			head = Node(x)
		else:
			new_node = head
			while new_node.next:
				new_node = new_node.next
			new_node.next = Node(x)
		return head


class Solution:

	def insertAtBegining(self, head, x):
		temp = Node(x)
		temp.next = head
		return temp

	def insertAtEnd(self, head, x):
		if head == None:
			return Node(x)
		temp = Node(x)
		cur = head
		while cur.next != None:
			cur = cur.next
		cur.next = temp
		return head


class Solution:

	def insertAtBegining(self, head, x):
		new = Node(x)
		if head:
			new.next = head
		head = new
		return head

	def insertAtEnd(self, head, x):
		new = Node(x)
		if head == None:
			head = new
		else:
			ln = head
			while ln.next:
				ln = ln.next
			ln.next = new
		return head


class Solution:

	def insertAtBegining(self, head, x):
		new_node = Node(x)
		if head != None:
			new_node.next = head
		head = new_node
		return head

	def insertAtEnd(self, head, x):
		new_node = Node(x)
		if head is None:
			head = new_node
			return head
		last = head
		while last.next:
			last = last.next
		last.next = new_node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		t = Node(x)
		if head == None:
			head = t
		else:
			t.next = head
			head = t
		return head

	def insertAtEnd(self, head, x):
		t = Node(x)
		t.next = None
		if head == None:
			head = t
		else:
			p = head
			while p.next != None:
				p = p.next
			p.next = t
		return head


class Solution:

	def insertAtBegining(self, head, x):
		if head is None:
			new_node = Node(x)
			head = new_node
			return new_node
		else:
			new_node = Node(x)
			new_node.next = head
			return new_node

	def insertAtEnd(self, head, x):
		if head is None:
			new_node = Node(x)
			head = new_node
			return new_node
		else:
			n = head
			while n.next is not None:
				n = n.next
			new_node = Node(x)
			n.next = new_node
			return head


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def insertAtBegining(self, head, x):
		new_node = Node(x)
		if head == None:
			head = new_node
			return head
		new_node.next = head
		head = new_node
		return head

	def insertAtEnd(self, head, x):
		new_node = Node(x)
		if head == None:
			head = new_node
			return head
		temp = head
		while temp.next:
			temp = temp.next
		temp.next = new_node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		n = Node(x)
		n.next = head
		return n

	def insertAtEnd(self, head, x):
		n = Node(x)
		if not head:
			return n
		p = head
		while p.next:
			p = p.next
		p.next = n
		return head


class Solution:

	def insertAtBegining(self, head, x):
		nodetoinsert = Node(x)
		if not head:
			head = nodetoinsert
		else:
			nodetoinsert.next = head
			head = nodetoinsert
		return head

	def insertAtEnd(self, head, x):
		nodetoinsert = Node(x)
		if not head:
			head = nodetoinsert
		else:
			temp = head
			while temp.next:
				temp = temp.next
			temp.next = nodetoinsert
		return head


class Solution:

	def insertAtBegining(self, head, x):
		new_node = Node(x)
		new_node.next = head
		head = new_node
		return head

	def insertAtEnd(self, head, x):
		new_node = Node(x)
		curr = head
		if head == None:
			return new_node
		while curr.next:
			curr = curr.next
		curr.next = new_node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		node = Node(x)
		node.next = head
		head = node
		return head

	def insertAtEnd(self, head, x):
		node = Node(x)
		temp = head
		if not temp:
			return node
		while temp.next:
			temp = temp.next
		temp.next = node
		temp = node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		new_Node = Node(x)
		if head == None:
			return new_Node
		new_Node.next = head
		return new_Node

	def insertAtEnd(self, head, x):
		new_Node = Node(x)
		if head == None:
			return new_Node
		dummy = head
		while dummy.next is not None:
			dummy = dummy.next
		dummy.next = new_Node
		return head


class Solution:

	def insertAtBegining(self, head, x):
		temp = Node(x)
		if head is None:
			head = temp
		else:
			temp.next = head
			head = temp
		return temp

	def insertAtEnd(self, head, x):
		temp = Node(x)
		if head is None:
			head = temp
		else:
			t = head
			while t.next != None:
				t = t.next
			t.next = temp
		return head


class Solution:

	def insertAtBegining(self, head, x):
		a = Node(x)
		a.next = head
		head = a
		return head

	def insertAtEnd(self, head, x):
		b = Node(x)
		if head is None:
			return b
		temp = head
		while temp.next:
			temp = temp.next
		temp.next = b
		return head


class Solution(object):

	def insertAtBegining(self, head, x):
		newNode = Node(x)
		newNode.next = head
		head = newNode
		return head

	def insertAtEnd(self, head, x):
		newNode = Node(x)
		if not head:
			return newNode
		curr = head
		while curr.next:
			curr = curr.next
		curr.next = newNode
		return head


class Solution(object):

	def insertAtBegining(self, head, x):
		if not head:
			head = Node(x)
		else:
			node = Node(x)
			node.next = head
			head = node
		return head

	def insertAtEnd(self, head, x):
		if not head:
			head = Node(x)
		else:
			curr = head
			while curr.next:
				curr = curr.next
			curr.next = Node(x)
		return head


class Solution:

	def insertAtBegining(self, head, x):
		node = Node(x)
		node.next = head
		return node

	def insertAtEnd(self, head, x):
		if head == None:
			return self.insertAtBegining(head, x)
		else:
			tmp = head
			while tmp.next:
				tmp = tmp.next
			tmp.next = Node(x)
			return head


class Solution:

	def insertAtBegining(self, head, x):
		if head == None:
			head = Node(x)
			return head
		a = head
		head = Node(x)
		head.next = a
		return head

	def insertAtEnd(self, head, x):
		if head == None:
			head = Node(x)
			return head
		a = head
		while a.next != None:
			a = a.next
		a.next = Node(x)
		return head


class Solution:

	def insertAtBegining(self, head, x):
		ind = Node(x)
		ind.next = head
		return ind

	def insertAtEnd(self, head, x):
		if head is None:
			return Node(x)
		ind = head
		while ind.next:
			ind = ind.next
		ind.next = Node(x)
		return head


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def insertAtBegining(self, head, x):
		newNode = Node(x)
		if head == None:
			return newNode
		newNode.next = head
		head = newNode
		return head

	def insertAtEnd(self, head, x):
		dummy = Node(x)
		if head is None:
			return dummy
		curr = head
		while curr.next != None:
			curr = curr.next
		curr.next = dummy
		return head