A number N is represented in Linked List such that each digit corresponds to a node in linked list. You need to add 1 to it.
Example 1:
Input:
LinkedList: 4->5->6
Output: 457 
Example 2:
Input:
LinkedList: 1->2->3
Output: 124 
Your Task:
Your task is to complete the function addOne() which takes the head of the linked list as the only argument and returns the head of the modified linked list. The driver code prints the number.
Note: The head represents the left-most digit of the number.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{21}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''



class Node:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None

'''



class Solution:

    def addOne(self,head):

        #Returns new head of linked List.

Solutions:
class Solution:

	def addOne(self, head):

		def reverse(head):
			(prev, curr) = (None, head)
			while curr:
				next = curr.next
				curr.next = prev
				prev = curr
				curr = next
			return prev
		if not head:
			return head
		revHead = prev = curr = reverse(head)
		carry = 1
		while curr:
			value = curr.data + carry
			curr.data = value % 10
			carry = value // 10
			prev = curr
			curr = curr.next
		if carry:
			prev.next = Node(carry)
		return reverse(revHead)


class Solution:

	def addOne(self, head):
		l = ''
		curr = head
		while curr:
			l += str(curr.data)
			curr = curr.next
		l = int(l)
		l += 1
		l = str(l)
		l = list(l)
		head = Node(int(l.pop(0)))
		curr = head
		while l:
			curr.next = Node(int(l.pop(0)))
			curr = curr.next
		return head


class Solution:

	def addOne(self, head):
		curr = head
		s = ''
		while curr:
			s += str(curr.data)
			curr = curr.next
		ans = Node(int(s) + 1)
		return ans


class Solution:

	def addOne(self, head):
		s = ''
		while head:
			s += str(head.data)
			head = head.next
		num = str(int(s) + 1)
		temp = Node(None)
		ans = temp
		for i in num:
			local = Node(int(i))
			temp.next = local
			temp = temp.next
		return ans.next


class Solution:

	def addOne(self, head):
		head = self.reverseLL(head)
		curr = head
		carry = 1
		while curr.next and carry:
			summ = curr.data + carry
			curr.data = summ % 10
			carry = summ // 10
			curr = curr.next
		curr.data = curr.data + carry if carry else curr.data
		head = self.reverseLL(head)
		return head

	def reverseLL(self, head):
		prev = None
		while head:
			curr = head
			head = head.next
			curr.next = prev
			prev = curr
		return prev


class Solution:

	def addOne(self, head):
		a = ''
		while head:
			a += str(head.data)
			head = head.next
		a = int(a)
		a = str(a + 1)
		a = list(a)
		dup = Node(-1)
		p = dup
		i = 0
		while i < len(a):
			dup.next = Node(a[i])
			dup = dup.next
			i += 1
		return p.next


def rev(head):
	(t, p) = (None, None)
	while head:
		t = head.next
		head.next = p
		p = head
		head = t
	return p

class Solution:

	def addOne(self, head):
		head = rev(head)
		i = 1
		ptr = head
		carry = 1
		l3 = Node(-1)
		p = l3
		while ptr or carry:
			result = carry
			if ptr:
				result += ptr.data
				ptr = ptr.next
			carry = result // 10
			p.next = Node(result % 10)
			p = p.next
		r = rev(l3.next)
		return r


class Solution:

	def addOne(self, head):
		s = Node(0)
		s.next = head
		temp = head
		l = 1
		c = 0
		while temp.next:
			if temp.data == 9:
				c += 1
			else:
				c = 0
			temp = temp.next
			l += 1
		if temp.data == 9:
			c += 1
			temp = s
			while c < l:
				temp = temp.next
				c += 1
			temp.data += 1
			while temp.next:
				temp = temp.next
				temp.data = 0
		else:
			temp.data += 1
		if s.data:
			return s
		else:
			return head


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def addOne(self, head):

		def addOneWitCarry(head):
			if head == None:
				return 1
			res = head.data + addOneWitCarry(head.next)
			head.data = int(res % 10)
			return int(res / 10)
		carry = addOneWitCarry(head)
		if carry == 1:
			newNode = Node(1)
			newNode.next = head
			return newNode
		return head


class Solution:

	def addOne(self, head):
		val = ''
		itr = head
		while itr:
			val += str(itr.data)
			itr = itr.next
		l = len(val)
		ans = str(int(val) + 1)
		if len(ans) == l:
			itr = head
			i = 0
			while itr:
				itr.data = ans[i]
				i += 1
				itr = itr.next
			return head
		else:
			temp = Node(0)
			temp.next = head
			itr = temp
			i = 0
			while itr:
				itr.data = ans[i]
				i += 1
				itr = itr.next
			return temp


class Solution:

	def addOne(self, head):
		num = ''
		tmp = head
		while tmp != None:
			num += str(tmp.data)
			tmp = tmp.next
		num = list(str(int(num) + 1))
		head = Node(num[0])
		tmp = head
		for i in range(1, len(num)):
			ins = Node(num[i])
			tmp.next = ins
			tmp = ins
		return head


class Solution:

	def addOne(self, head):
		ans = 0
		num = ''
		curr = head
		while curr.next:
			num += str(curr.data)
			curr = curr.next
		num += str(curr.data)
		ans = int(num) + 1
		newhead = Node(None)
		curr = newhead
		for digit in str(ans):
			curr.next = Node(int(digit))
			curr = curr.next
		return newhead.next


class Solution:

	def addOne(self, head):
		front = head
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		head1 = prev
		front = prev
		c = 0
		prev = None
		while front is not None:
			if prev is None:
				if front.data + c + 1 >= 10:
					t = (front.data + 1 + c) // 10
					front.data = (front.data + 1 + c) % 10
					c = t
				else:
					front.data = front.data + 1 + c
					c = 0
			elif front.data + c >= 10:
				t = (front.data + c) // 10
				front.data = (front.data + c) % 10
				c = t
			else:
				front.data = front.data + c
				c = 0
			prev = front
			front = front.next
		if c > 0:
			prev.next = Node(c)
		front = head1
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		return prev


class Solution:

	def reverse(self, head):
		n = head
		prev = None
		while n is not None:
			temp = n.next
			n.next = prev
			prev = n
			n = temp
		head = prev
		return head

	def addOne(self, head):
		if not head:
			return None
		head = self.reverse(head)
		new_head = head
		carry = 0
		add_one = 1
		l_prev = None
		prev = None
		while new_head is not None:
			sum_ = carry + new_head.data + add_one
			if sum_ >= 10:
				carry = sum_ // 10
				sum_ = sum_ % 10
			else:
				carry = 0
			new_head.data = sum_
			add_one = 0
			temp = new_head.next
			new_head.next = prev
			prev = new_head
			new_head = temp
		if carry:
			new_node = Node(carry)
			new_node.next = prev
			head = new_node
		else:
			head = prev
		return head


class Solution:

	def rev(self, head):
		if head == None:
			return head
		if head.next == None:
			return head
		r = head
		head = head.next
		r.next = None
		while head != None:
			temp = r
			r = head
			head = head.next
			r.next = None
			r.next = temp
		return r

	def addOne(self, head):
		if head.next == None:
			ans = Node((1 + head.data) // 10)
			ans.next = Node((1 + head.data) % 10)
			if ans.data == 0:
				ans = ans.next
			return ans
		head = self.rev(head)
		a = Node(-1)
		ans = a
		c = 1
		while head != None:
			d = c + head.data
			ans.next = Node(d % 10)
			c = d // 10
			head = head.next
			ans = ans.next
		ans.next = Node(c)
		ans = self.rev(a.next)
		while ans.data == 0:
			ans = ans.next
		return ans


class Solution:

	def addOne(self, head):
		curr = head
		prev = None
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		head = prev
		carry = 1
		curr = head
		while curr and carry:
			sum = curr.data + carry
			curr.data = sum % 10
			carry = sum // 10
			prev = curr
			curr = curr.next
		if carry:
			prev.next = Node(carry)
		curr = head
		prev = None
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		head = prev
		return head


class Solution:

	def addOne(self, head):
		k = head
		i = 0
		j = 0
		while k:
			i = i + 1
			k = k.next
		c = head
		prev = None
		while c:
			n = c.next
			c.next = prev
			prev = c
			c = n
		head = prev
		cur = head
		while cur:
			if cur.data <= 8:
				cur.data = cur.data + 1
				break
			else:
				cur.data = 0
				j = j + 1
				l = cur
				cur = cur.next
		if i == j:
			l.next = Node(1)
		c1 = head
		prev1 = None
		while c1:
			n1 = c1.next
			c1.next = prev1
			prev1 = c1
			c1 = n1
		return prev1


class Solution:

	def reverse(self, head):
		prev = None
		current = head
		next = head.next
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		return prev

	def addOne(self, head):
		head = self.reverse(head)
		current = head
		carry = 1
		while carry:
			current.data += 1
			if current.data < 10:
				return self.reverse(head)
			else:
				current.data = 0
			if current.next is None:
				break
			else:
				current = current.next
		current.next = Node(1)
		return self.reverse(head)


class Solution:

	def addOne(self, head):

		def printList(head):
			while head:
				print(head.data, end='->')
				head = head.next
			print('None')

		def reverse(head):
			if not head or not head.next:
				return head
			pre = None
			cur = head
			while cur:
				nex = cur.next
				cur.next = pre
				pre = cur
				cur = nex
			return pre
		head = reverse(head)
		pre = None
		cur = head
		carry = 0
		cur.data += 1
		while cur:
			temp = cur.data + carry
			cur.data = int(temp % 10)
			carry = int(temp / 10)
			pre = cur
			cur = cur.next
		if carry:
			pre.next = Node(carry)
		return reverse(head)


class Solution:

	def addOne(self, head):
		x = str()
		while head:
			x += str(head.data)
			head = head.next
		x = str(int(x) + 1)
		x = list(x)
		head = Node(x[0])
		cur = head
		for i in range(1, len(x)):
			cur.next = Node(x[i])
			cur = cur.next
		return head


class Solution:

	def addOne(self, head):
		a = ''
		cur = head
		while cur:
			a += str(cur.data)
			cur = cur.next
		a = int(a) + 1
		d = Node(0)
		h = d
		if a == 0:
			return d
		while a:
			l = Node(a % 10)
			a = a // 10
			d.next = l
			d = d.next
		prev = None
		cur = h.next
		while cur:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
		return prev


class Solution:

	def addOne(self, head):
		if not head:
			return head
		if head.next == None:
			if head.data < 9:
				head.data = head.data + 1
				return head
			else:
				dummy = Node(1)
				head.data = 0
				dummy.next = head
				return dummy
		p = head
		q = head.next
		while q:
			p.next = q.next
			q.next = head
			head = q
			q = p.next
		if head.data < 9:
			head.data += 1
		elif head.data == 9:
			head.data = 0
			prev = head
			ptr = head.next
			while ptr and ptr.data == 9:
				ptr.data = 0
				prev = ptr
				ptr = ptr.next
			if ptr:
				ptr.data = ptr.data + 1
			else:
				dummy = Node(1)
				prev.next = dummy
		p = head
		q = head.next
		while q:
			p.next = q.next
			q.next = head
			head = q
			q = p.next
		return head


class Solution:

	def addOne(self, head):
		s = ''
		cur = head
		while cur:
			s += str(cur.data)
			cur = cur.next
		sum = str(int(s) + 1)
		x = Node(0)
		dummy = x
		t = 0
		while t < len(sum):
			dummy.next = Node(int(sum[t]))
			t += 1
			dummy = dummy.next
		return x.next


class Solution:

	def reverse(self, head):
		prev = None
		curr = head
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev

	def addOne(self, head):
		rev = self.reverse(head)
		curr = rev
		s = curr.data + 1
		curr.data = s % 10
		carry = s // 10
		prev = curr
		curr = curr.next
		while curr:
			s = curr.data + carry
			curr.data = s % 10
			carry = s // 10
			prev = curr
			curr = curr.next
		if carry != 0:
			prev.next = Node(carry)
		return self.reverse(rev)


class Solution:

	def reverse(self, head):
		prev = None
		n = None
		curr = head
		while curr is not None:
			n = curr.next
			curr.next = prev
			prev = curr
			curr = n
		return prev

	def addOne(self, head):
		if head.next is None:
			head.data += 1
			return head
		newHead = self.reverse(head)
		curr = newHead
		carry = 0
		if curr.data + 1 == 10:
			carry = 1
			curr.data = 0
		else:
			curr.data += 1
		curr = curr.next
		while curr:
			if carry:
				curr.data += 1
				carry = 0
			if curr.data == 10 and curr.next is None:
				break
			if curr.data == 10:
				carry = 1
				curr.data = 0
			curr = curr.next
		return self.reverse(newHead)


class Solution:

	def addOne(self, head):

		def reverse(root):
			curr = root
			prev = None
			while curr:
				next = curr.next
				curr.next = prev
				prev = curr
				curr = next
			return prev
		r = reverse(head)
		curr = r
		carry = 1
		while curr:
			v = curr.data + carry
			if v <= 9:
				curr.data = v
				return reverse(r)
			else:
				curr.data = 0
				carry = 1
			prev = curr
			curr = curr.next
		if carry:
			prev.next = Node(1)
		return reverse(r)


class Solution:

	def addOne(self, head):

		def prnt(c):
			curr = c
			while curr:
				print(curr.data, end='->')
				curr = curr.next

		def rev(curr):
			dummy = None
			while curr:
				temp = curr.next
				curr.next = dummy
				dummy = curr
				curr = temp
			return dummy
		curr = rev(head)
		travel = curr
		carry = 1
		prev = None
		while travel and carry:
			prev = travel
			if travel.data == 9:
				travel.data = 0
				travel = travel.next
			else:
				travel.data = travel.data + carry
				carry = 0
		if carry:
			prev.next = Node(carry)
		return rev(curr)
		prnt(curr)
		print()
		prnt(rev(curr))


class Solution:

	def addOne(self, head):
		x = 0
		tmp = head
		while tmp:
			x = x * 10 + tmp.data
			tmp = tmp.next
		x += 1
		li = []
		while x != 0:
			li.append(x % 10)
			x = x // 10
		ll = LinkedList()
		for i in li[-1::-1]:
			ll.insert(i)
		return ll.head


class Solution:

	def addOne(self, head):
		head_val = str(head.data)
		next_node = head
		while next_node.next:
			head_val = head_val + str(next_node.next.data)
			if next_node.next.next:
				next_node.next = next_node.next.next
			else:
				next_node.next = None
		head.data = int(head_val) + 1
		return head


class Solution:

	def addOne(self, head):
		st = []
		curr = head
		while curr.next is not None:
			st.append(curr)
			curr = curr.next
		if curr.data < 9:
			curr.data += 1
			return head
		else:
			if len(st) <= 0:
				curr.data += 1
				return head
			curr.data = 0
			bal = 1
			while len(st):
				curr = st.pop()
				if len(st) == 0:
					curr.data += 1
					return head
				elif curr.data < 9:
					curr.data += 1
					return head
				else:
					curr.data = 0
					bal = 1
		return head


def reverse(cur):
	pre = None
	while cur:
		t = cur.next
		cur.next = pre
		pre = cur
		cur = t
	return pre

class Solution:

	def addOne(self, head):
		new = reverse(head)
		temp = new
		while temp:
			if temp.data == 9 and temp.next == None:
				temp.data = 0
				newNode = Node(1)
				temp.next = newNode
				break
			elif temp.data == 9:
				temp.data = 0
				temp = temp.next
			else:
				temp.data = temp.data + 1
				break
		return reverse(new)


class Solution:

	def addit(self, head):
		if head.next is None:
			sumval = head.data + 1
			head.data = sumval % 10
			return sumval // 10
		carry = self.addit(head.next)
		sumval = head.data + carry
		head.data = sumval % 10
		return sumval // 10

	def addOne(self, head):
		c = self.addit(head)
		if c != 0:
			node = Node(c)
			node.next = head
			return node
		return head


class Solution:

	def addOne(self, head):
		s = ''
		while head:
			s += str(head.data)
			head = head.next
		s = int(s)
		s = s + 1
		s = str(s)
		s = list(s)
		dummy = Node(-1)
		p = dummy
		i = 0
		while i < len(s):
			dummy.next = Node(s[i])
			dummy = dummy.next
			i += 1
		return p.next


class Solution:

	def reverseLL(self, head):
		prev = None
		curr = head
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		head = prev
		return prev

	def addOne(self, head):
		if head.next is None:
			head.data += 1
			return head
		reverse_head = self.reverseLL(head)
		carry = 0
		temp = reverse_head
		temp.data += 1
		while temp:
			temp.data += carry
			if temp.next is None:
				break
			if temp.data == 10:
				temp.data = 0
				carry = 1
				temp = temp.next
			else:
				break
		return self.reverseLL(reverse_head)


class Solution:

	def addOne(self, head):
		num = 0
		curr = head
		while curr:
			num = num * 10 + curr.data
			curr = curr.next
		num += 1
		dummy = Node(0)
		curr = dummy
		for digit in str(num):
			curr.next = Node(int(digit))
			curr = curr.next
		return dummy.next


class Solution:

	def addOne(self, head):
		temp = head
		ans = ''
		while temp != None:
			ans += str(temp.data)
			temp = temp.next
		sol = int(ans) + 1
		return Node(sol)


class Solution:

	def addOne(self, head):
		num = self.reverseNum(head)
		s = Node(-1)
		temp = s
		carry = 1
		while num:
			num.data += carry
			carry = num.data // 10
			num.data = num.data % 10
			temp.next = num
			temp = num
			num = num.next
		if carry == 1:
			node = Node(1)
			temp.next = node
		s = s.next
		return self.reverseNum(s)

	def reverseNum(self, head):
		if not head or not head.next:
			return head
		tail = head.next
		newHead = self.reverseNum(head.next)
		tail.next = head
		head.next = None
		return newHead


class Solution:

	def addOne(self, first):

		def reverse(head):
			prev = None
			current = head
			while current is not None:
				temp = current.next
				current.next = prev
				prev = current
				current = temp
			head = prev
			return head
		first = reverse(first)
		second = Node(1)
		dummy = Node(0)
		temp = dummy
		carry = 0
		while first or second or carry == 1:
			s = 0
			if first:
				s += first.data
				first = first.next
			if second:
				s += second.data
				second = second.next
			s += carry
			carry = s // 10
			newNode = Node(s % 10)
			temp.next = newNode
			temp = temp.next
		return reverse(dummy.next)


class Solution:

	def addOne(self, head):

		def reverseList(head1):
			curr = head1
			prev = None
			while curr != None:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		head2 = reverseList(head)
		sum = head2.data + 1
		val = sum % 10
		carry = sum // 10
		head2.data = val
		temp = head2
		prev = head2
		head2 = head2.next
		while carry != 0 and head2 != None:
			sum = head2.data + carry
			val = sum % 10
			carry = sum // 10
			head2.data = val
			prev = head2
			head2 = head2.next
		if carry != 0:
			nn = Node(carry)
			prev.next = nn
			prev = prev.next
		head = reverseList(temp)
		return head


import sys
sys.setrecursionlimit(10 ** 4)

class Solution:

	def add(this, root):
		if root.next != None:
			rem = this.add(root.next)
			root.data += rem
			temp = root.data % 10
			temp2 = (root.data - temp) // 10
			root.data = temp
			return temp2
		rem = 1
		root.data += rem
		temp = root.data % 10
		temp2 = (root.data - temp) // 10
		root.data = temp
		return temp2

	def addOne(self, head):
		rem = self.add(head)
		if rem == 0:
			return head
		new_head = Node(1)
		new_head.next = head
		return new_head


class Solution:

	def addOne(self, head):
		prev = None
		current = head
		while current:
			new = current.next
			current.next = prev
			prev = current
			current = new
		current = prev
		carry = 1
		while current and carry:
			sum = current.data + carry
			current.data = sum % 10
			carry = sum // 10
			current = current.next
		previous = None
		current = prev
		while current:
			new = current.next
			current.next = previous
			previous = current
			current = new
		if carry:
			newnode = Node(1)
			newnode.next = previous
			previous = newnode
		return previous


class Solution:

	def solve(self, head, carry):
		if head.next == None:
			a = head.data
			head.data = (carry[0] + a + 1) % 10
			carry[0] = (carry[0] + a + 1) // 10
			return
		self.solve(head.next, carry)
		if head.next != None:
			a = head.data
			head.data = (carry[0] + a) % 10
			carry[0] = (carry[0] + a) // 10
		return head

	def reverse(self, head):
		prev = nxt = None
		curr = head
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		return prev

	def addOne(self, head):
		head = self.reverse(head)
		curr = head
		carry = (curr.data + 1) // 10
		curr.data = (curr.data + 1) % 10
		curr = curr.next
		while curr:
			a = curr.data
			curr.data = (carry + a) % 10
			carry = (carry + a) // 10
			curr = curr.next
		head = self.reverse(head)
		if carry > 0:
			node = Node(carry)
			node.next = head
			head = node
		return head


class Solution:

	def addOne(self, head):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		s = ''.join(map(str, l))
		i = int(s) + 1
		l1 = list(str(i))
		p = []
		for i in l1:
			p.append(Node(i))
		p.append(None)
		head = cur = p[0]
		for i in range(1, len(p)):
			cur.next = p[i]
			cur = cur.next
		return head


class Solution:

	def addOne(self, head):
		s = ''
		while head is not None:
			s += str(head.data)
			head = head.next
		ans = Node(int(s) + 1)
		return ans


class Solution:

	def addOne(self, head):
		if head.next is None:
			head.data = head.data + 1
			return head
		L = []
		n = head
		while n is not None:
			L.append(n.data)
			n = n.next
		L.reverse()
		for i in range(0, len(L) - 1):
			if L[i] + 1 == 10:
				L[i] = 0
			else:
				L[i] = L[i] + 1
				break
		if L[i] == 0:
			L[i + 1] = L[i + 1] + 1
		L.reverse()
		n = head
		while n is not None:
			n.data = L.pop(0)
			n = n.next
		return head


class Solution:

	def addOne(self, head):
		a = []
		while head != None:
			a.append(head.data)
			head = head.next
		res = int(''.join([str(i) for i in a]))
		x = res + 1
		print(x, end=' ')


class Solution:

	def addOne(self, head):
		itr = head
		l = ''
		while itr:
			l += str(itr.data)
			itr = itr.next
		l = str(int(l) + 1)
		head1 = Node(l[0])
		t = head1
		for i in range(1, len(l)):
			x = Node(l[i])
			head1.next = x
			head1 = head1.next
		return t


class Solution:

	def addOne(self, head):
		h = head
		c = 0
		while h:
			c = c * 10 + h.data
			h = h.next
		c = str(c + 1)
		h = head
		k = 0
		while h.next:
			h.data = int(c[k])
			h = h.next
			k += 1
		h.data = c[k]
		k += 1
		while k < len(c):
			h.next = Node(data=int(c[k]))
			h = h.next
			k += 1
		return head


class Solution:

	def reverse(self, rest):
		node = None
		while rest:
			next = rest.next
			rest.next = node
			node = rest
			rest = next
		return node

	def addOne(self, head):
		head = self.reverse(head)
		node = head
		done = False
		while node:
			if node.data < 9:
				node.data += 1
				done = True
				break
			else:
				node.data = 0
				node = node.next
		head = self.reverse(head)
		if not done:
			new_head = Node(1)
			new_head.next = head
			return new_head
		return head


class Solution:

	def addOne(self, head):

		def rev(head):
			prev = None
			curr = head
			while curr:
				next = curr.next
				curr.next = prev
				prev = curr
				curr = next
			return prev
		h1 = rev(head)
		curr = h1
		carry = 1
		while curr.next and carry:
			s = curr.data + carry
			curr.data = s % 10
			carry = s // 10
			curr = curr.next
		if carry:
			curr.data = curr.data + carry
		else:
			curr.data = curr.data
		h2 = rev(h1)
		return h2


class Solution:

	def addOne(self, head):
		s = ''
		ptr = head
		while ptr:
			s += str(ptr.data)
			ptr = ptr.next
		s = str(int(s) + 1)
		a = b = Node(0)
		x = 0
		while x < len(s):
			a.data = s[x]
			x += 1
			if x < len(s):
				a.next = Node(0)
				a = a.next
		return b


class Solution:

	def reverse(self, head):
		prev = None
		while head:
			nex = head.next
			head.next = prev
			prev = head
			head = nex
		return prev

	def addOne(self, head):
		rev = self.reverse(head)
		cur = prev = rev
		while cur:
			cur.data += 1
			if cur.data == 10:
				cur.data = 0
			else:
				break
			prev = cur
			cur = cur.next
		if not cur:
			prev.next = Node(1)
		res = self.reverse(rev)
		return res


class Solution:

	def addOne(self, head):
		a = head
		g = head
		l = 0
		s = ''
		while a != None:
			l += 1
			s += str(a.data)
			a = a.next
		s = int(s)
		ans = str(s + 1)
		temp = Node(ans[0])
		loc = 0
		flag = 0
		if len(ans) > l:
			temp.next = head
			head = temp
			loc += 1
			flag = 1
		if flag == 0:
			while loc < l:
				g.data = ans[loc]
				g = g.next
				loc += 1
		if flag == 1:
			while loc <= l:
				g.data = ans[loc]
				g = g.next
				loc += 1
		return head


class Solution:

	def addOne(self, head):
		s = ''
		while head:
			s = s + str(head.data)
			head = head.next
		s = str(int(s) + 1)
		z = Node(s[0])
		next_node = z
		for i in s[1:]:
			next_node.next = Node(i)
			next_node = next_node.next
		return z


class Solution:

	def addOne(self, head):
		cur = head
		l = []
		while head != None:
			l.append(str(head.data))
			head = head.next
		s = ''.join(l)
		n = int(s)
		n += 1
		t = list(str(n))
		a = Node(0)
		b = a
		for i in range(len(t)):
			c = Node(t[i])
			a.next = c
			a = a.next
		return b.next


class Solution:

	def reverseList(self, head):
		curr = head
		prev = None
		_next = None
		while curr is not None:
			_next = curr.next
			curr.next = prev
			prev = curr
			curr = _next
		return prev

	def printList(self, head):
		while head is not None:
			print(head.data, sep='->', end='')
			head = head.next
		print('NULL')

	def addOne(self, head):
		if head.next is None and head.data == 9:
			head.data = 1
			head.next = Node(0)
			return head
		newhead = self.reverseList(head)
		_data = newhead.data
		_data += 1
		carry = _data // 10
		_data %= 10
		newhead.data = _data
		temp = newhead.next
		while carry != 0:
			if temp is None:
				break
			if temp.next is None:
				_data = temp.data
				_data += carry
				carry = _data // 10
				_data %= 10
				temp.data = _data
				break
			_data = temp.data
			_data += carry
			carry = _data // 10
			_data %= 10
			temp.data = _data
			temp = temp.next
		if carry != 0:
			temp.next = Node(carry)
		return self.reverseList(newhead)


class Solution:

	def addOne(self, head):
		num = ''
		while head != None:
			num += str(head.data)
			head = head.next
		linked_list = LinkedList()
		linked_list.head = Node(int(num) + 1)
		return linked_list.head


class Solution:

	def reverse(self, head):
		if head is None:
			return None
		prev = None
		current = head
		next = current.next
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		return prev

	def addOne(self, head):
		temp = head
		ob = Solution()
		revhead = ob.reverse(temp)
		curr = revhead
		carry = 1
		while curr.next:
			k = curr.data
			if k + carry < 10:
				curr.data = curr.data + carry
				carry = 0
			else:
				curr.data = 0
				carry = 1
			curr = curr.next
		if curr.data + carry < 10:
			curr.data = curr.data + carry
		else:
			curr.data = 0
			curr.next = Node(1)
		org = ob.reverse(revhead)
		return org


class Solution:

	def addOne(self, head):
		prev = None
		curr = head
		thead = head
		while thead:
			curr = thead
			thead = thead.next
			curr.next = prev
			prev = curr
		add = 1
		carry = 0
		thead = curr
		while thead:
			if add > 0:
				thead.data += 1
				add = 0
			if carry > 0:
				thead.data += carry
				carry = 0
			if thead.data > 9:
				thead.data = 0
				carry = 1
			elif thead.data <= 9:
				carry = 0
			prev = thead
			thead = thead.next
		if carry:
			prev.next = Node(carry)
		prev = None
		curr = curr
		thead = curr
		while thead:
			curr = thead
			thead = thead.next
			curr.next = prev
			prev = curr
		return curr


class Solution:

	def addOne(self, head):
		p = []
		a = head
		while a is not None:
			p.append(a.data)
			a = a.next
		m = ''.join([str(i) for i in p])
		q = int(m) + 1
		list2 = [int(i) for i in str(q)]
		head1 = None
		b = None
		for i in list2:
			new = Node(i)
			if head1 == None:
				head1 = new
				b = head1
			else:
				head1.next = new
				head1 = head1.next
		return b


class Solution:

	def addOne(self, head):
		temp = head
		num = 0
		while temp:
			num = num * 10 + temp.data
			temp = temp.next
		num += 1
		num = list(str(num))
		head = Node(num[0])
		temp = head
		for i in range(1, len(num)):
			temp.next = Node(num[i])
			temp = temp.next
		return head


class Solution:

	def reverse(self, head):
		nxt = None
		prev = None
		current = head
		while current != None:
			nxt = current.next
			current.next = prev
			prev = current
			current = nxt
		head = prev
		return head

	def show_link_list(self, head):
		current = head
		while current != None:
			print(current.data)
			current = current.next

	def addOne(self, head):
		rev_link_list = self.reverse(head)
		current = rev_link_list
		carry = 0
		current.data = current.data + 1
		while current != None and (current.data > 9 or carry > 0):
			prev = current
			current.data += carry
			carry = current.data // 10
			current.data = current.data % 10
			current = current.next
		if carry > 0:
			prev.next = Node(carry)
		return self.reverse(rev_link_list)


class Solution:

	def addOne(self, head):

		def reverse(head):
			prev = None
			while head:
				temp = head.next
				head.next = prev
				prev = head
				head = temp
			return prev
		node = reverse(head)
		carry = 1
		temp = node
		while temp:
			prev = temp
			x = temp.data + carry
			temp.data = x % 10
			carry = x // 10
			temp = temp.next
		if carry == 1:
			prev.next = Node(1)
		res = reverse(node)
		return res


class Solution:

	def addOne(self, head):
		a = ''
		temp = head
		while temp:
			a += str(temp.data)
			temp = temp.next
		a = int(a)
		return Node(a + 1)


import math
import sys
sys.setrecursionlimit(1002)

class Solution:

	def addOne(self, head):
		first_carry = self.recurse(head)
		if first_carry:
			new_head = Node(1)
			new_head.next = head
			return new_head
		else:
			return head

	def recurse(self, head):
		if head is None:
			return 0
		carry = self.recurse(head.next)
		if head.next is None:
			head.data += 1
		if carry > 0:
			head.data += 1
		if head.data == 10:
			head.data = 0
			return 1
		else:
			return 0


class Solution:

	def reverse(self, head):
		pre = None
		while head != None:
			next = head.next
			head.next = pre
			pre = head
			head = next
		return pre

	def addOne(self, head):
		head = self.reverse(head)
		head.data += 1
		result = head
		while head.data >= 10:
			head.data -= 10
			if head.next == None:
				head.next = Node(0)
			head = head.next
			head.data += 1
		return self.reverse(result)


class Solution:

	def addOne(self, head):
		n = ''
		while head:
			n += str(head.data)
			head = head.next
		n = int(n)
		n = str(n + 1)
		n = list(n)
		dummy = Node(-1)
		x = dummy
		i = 0
		while i < len(n):
			dummy.next = Node(n[i])
			dummy = dummy.next
			i += 1
		return x.next


class Solution:

	def reverse(self, head):
		if head is None or head.next is None:
			return head
		pre = None
		cur = head
		while cur is not None:
			t = cur.next
			cur.next = pre
			pre = cur
			cur = t
		return pre

	def addOne(self, head):
		if head is None:
			return Node(1)
		t = self.reverse(head)
		c = 1
		cur = t
		pre = None
		while cur is not None:
			if c == 1:
				cur.data += 1
			if cur.data > 9:
				cur.data = 0
				c = 1
			else:
				c = 0
				return self.reverse(t)
			pre = cur
			cur = cur.next
		if c == 1:
			te = Node(1)
			if pre is not None:
				pre.next = te
				return self.reverse(t)
			return self.reverse(t)
		else:
			return self.reverse(t)


class Solution:

	def addOne(self, head):
		newHead = self.reverse(head)
		temp = newHead
		while temp.next != None and temp.data == 9:
			temp.data = 0
			temp = temp.next
		if temp.data != 9:
			temp.data += 1
		elif temp.next == None and temp.data == 9:
			temp.data = 0
			temp.next = Node(1)
		return self.reverse(newHead)

	def reverse(self, head):
		prev = None
		curr = head
		while curr != None:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		head = prev
		return head


class Solution:

	def addOne(self, head):
		temp = head
		sum1 = 0
		cnt = 0
		while temp != None:
			sum1 = sum1 * 10 + temp.data
			cnt += 1
			temp = temp.next
		temp = head
		sum1 += 1
		while cnt != 0:
			temp.data = sum1 // pow(10, cnt - 1)
			cnt -= 1
			sum1 = sum1 - temp.data * pow(10, cnt)
			temp = temp.next
		return head


class Solution:

	def addOne(self, head):
		temp = head
		num = ''
		while temp:
			num += str(temp.data)
			temp = temp.next
		num = int(num) + 1
		head = prev = None
		while num > 0:
			rem = num % 10
			node = Node(rem)
			node.next = prev
			head = node
			prev = head
			num = num // 10
		return head


class Solution:

	def addOne(self, head):
		prev = None
		cur = head
		while cur:
			temp = cur.next
			cur.next = prev
			prev = cur
			cur = temp
		head = prev
		temp = head
		carry = 1
		prev = None
		while temp:
			temp.data = temp.data + carry
			if temp.data == 10:
				temp.data = 0
				carry = 1
			else:
				carry = 0
				break
			prev = temp
			temp = temp.next
		if carry == 1:
			node = Node(1)
			prev.next = node
		prev = None
		cur = head
		while cur:
			temp = cur.next
			cur.next = prev
			prev = cur
			cur = temp
		head = prev
		return head


class Solution:

	def addOne(self, head):
		curr = head
		prvs = None
		while curr != None:
			nxt = curr.next
			curr.next = prvs
			prvs = curr
			curr = nxt
		curr = prvs
		while prvs.data == 9 and prvs.next != None:
			prvs.data = 0
			prvs = prvs.next
		prvs.data += 1
		prvs = None
		while curr != None:
			nxt = curr.next
			curr.next = prvs
			prvs = curr
			curr = nxt
		return prvs


class Solution:

	def addOne(self, head):
		if head == None:
			return Node(1)
		temp = head
		s = 0
		while temp != None:
			s = s * 10 + temp.data
			temp = temp.next
		s = s + 1
		s = str(s)
		newhead = Node(s[0])
		temp = newhead
		for i in s[1:]:
			temp.next = Node(i)
			temp = temp.next
		return newhead


class Solution:

	def addOne(self, head):
		curr = head
		start9 = None
		prev9 = None
		flag = 0
		while curr.next:
			if curr.data == 9:
				if flag == 0:
					flag = 1
					start9 = curr
			else:
				if flag == 1:
					flag = 0
					start9 = None
				prev9 = curr
			curr = curr.next
		if curr.data != 9:
			curr.data += 1
			return head
		else:
			if flag == 0:
				curr.data = 0
			else:
				while start9:
					start9.data = 0
					start9 = start9.next
			if prev9 == None:
				node = Node(1)
				node.next = head
				head = node
			else:
				prev9.data += 1
			return head


class Solution:

	def addOne(self, head):
		num = ''
		cur = head
		while cur != None:
			num += str(cur.data)
			cur = cur.next
		res = int(num) + 1
		a = n = Node(0)
		for i in str(res):
			n.next = Node(int(i))
			n = n.next
		return a.next


class Solution:

	def addOne(self, head):
		rev = self.reverse(head)
		tmp = rev
		carry = 1
		while tmp:
			val = tmp.data + carry
			if val >= 10:
				carry = 1
				tmp.data = val % 10
			else:
				tmp.data = val
				carry = 0
			tmp = tmp.next
		if carry == 1:
			head = self.reverse(rev)
			newNode = Node(carry)
			newNode.next = head
			head = newNode
			return head
		return self.reverse(rev)

	def reverse(self, head):
		prev = None
		current = head
		while current:
			nxt = current.next
			current.next = prev
			prev = current
			current = nxt
		return prev


class Solution:

	def addOne(self, head):
		num = head.data
		curr = head.next
		while curr != None:
			num = num * 10 + curr.data
			curr = curr.next
		head.data = num + 1
		head.next = None
		return head


class Solution:

	def addOne(self, head):
		self.head = head
		temp = self.head
		prev = Node(temp.data)
		count = 1
		count_9 = 0
		if temp.data == 9:
			count_9 += 1
		temp = temp.next
		while temp is not None:
			curr = Node(temp.data)
			if temp.data == 9:
				count_9 += 1
			count += 1
			curr.next = prev
			prev = curr
			temp = temp.next
		duphead = prev
		temp = duphead
		while temp is not None:
			if temp.data < 9:
				temp.data += 1
				break
			elif temp.data == 9:
				temp.data = 0
				temp = temp.next
		curr = duphead
		temp = curr
		prev = Node(temp.data)
		temp = temp.next
		while temp is not None:
			curr = Node(temp.data)
			curr.next = prev
			prev = curr
			temp = temp.next
		self.head = prev
		if count == count_9:
			node = Node(1)
			node.next = self.head
			self.head = node
		return self.head


class Solution:

	def reverseList(self, head):
		if not head:
			return
		curNode = head
		prevNode = head
		nextNode = head.next
		curNode.next = None
		while nextNode:
			curNode = nextNode
			nextNode = nextNode.next
			curNode.next = prevNode
			prevNode = curNode
		return curNode

	def addOne(self, head):
		head = Solution().reverseList(head)
		k = head
		carry = 0
		prev = None
		head.data += 1
		while head != None and (head.data > 9 or carry > 0):
			prev = head
			head.data += carry
			carry = head.data // 10
			head.data = head.data % 10
			head = head.next
		if carry > 0:
			prev.next = Node(carry)
		return Solution().reverseList(k)


import sys
sys.setrecursionlimit(1001)

def rec(head):
	if not head:
		return 1
	res = rec(head.next)
	ans = head.data + res
	if ans == 10:
		head.data = 0
		return 1
	else:
		head.data = ans
		return 0

class Solution:

	def addOne(self, head):
		ans = rec(head)
		if ans:
			temp = Node(1)
			temp.next = head
			head = temp
		return head


class Solution:

	def addOne(self, head):
		head = self.reverse(head)
		cur = head
		prev = head
		sum = cur.data + 1
		cur.data = sum % 10
		carry = sum // 10
		cur = cur.next
		while cur != None:
			sum = cur.data + carry
			cur.data = sum % 10
			carry = sum // 10
			prev = cur
			cur = cur.next
		if carry != 0:
			prev.next = Node(carry)
		head = self.reverse(head)
		return head

	def reverse(self, head):
		prev = None
		cur = head
		while cur:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		head = prev
		return prev


class Solution:

	def addOne(self, head):
		s = ''
		p = head
		while p:
			s = s + str(p.data)
			p = p.next
		s = int(s)
		s = s + 1
		s = str(s)
		n = len(s)
		newhead = None
		tail = None
		i = 0
		while i < n:
			if newhead == None:
				q = int(s[0])
				newhead = tail = Node(q)
			else:
				q = int(s[i])
				tail.next = Node(q)
				tail = tail.next
			i = i + 1
		return newhead


class Solution:

	def addOne(self, head):
		ln = head
		if head.next == None:
			head.data += 1
			return head
		t = head
		prev = 0
		while t.next != None:
			if t.data != 9:
				ln = t
			t = t.next
		if t.data == 9 and ln != None:
			t = ln
			t.data += 1
			t = t.next
			while t != None:
				t.data = 0
				t = t.next
		else:
			t.data += 1
		return head


class Solution:

	def addOne(self, head):

		def reverse(node):
			before = None
			current = node
			after = current.next
			while after:
				current.next = before
				before = current
				current = after
				after = after.next
			current.next = before
			head = current
			return head
		x = reverse(head)
		y = x
		while x:
			if x.data == 9:
				x.data = 0
				x = x.next
			else:
				x.data += 1
				break
		if x == None:
			ans = reverse(y)
			temp = Node(1)
			temp.next = ans
			return temp
		else:
			ans = reverse(y)
		return ans


class Solution:

	def addOne(self, head):
		rev = self.reverse(head)
		carry = 0
		sum = rev.data + 1
		new1 = Node(sum % 10)
		carry = sum // 10
		head1 = new1
		temp = new1
		rev = rev.next
		while rev or carry:
			sum = 0
			if rev:
				sum += rev.data
				rev = rev.next
			sum += carry
			carry = sum // 10
			new2 = Node(sum % 10)
			temp.next = new2
			temp = new2
		ans = self.reverse(head1)
		return ans

	def reverse(self, head):
		prev = None
		curr = head
		nex = head
		while curr:
			nex = curr.next
			curr.next = prev
			prev = curr
			curr = nex
		return prev


class Solution:

	def addOne(self, head):
		head = self.reverse(head)
		temp = head
		prev = None
		if temp.data == 9:
			while temp != None and temp.data == 9:
				temp.data = 0
				prev = temp
				temp = temp.next
			if temp is None:
				new = Node(1)
				prev.next = new
			else:
				temp.data = temp.data + 1
		else:
			temp.data = temp.data + 1
		head = self.reverse(head)
		return head

	def reverse(self, head):
		curr = head
		prev = None
		next = None
		while curr is not None:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		curr = prev
		return curr