Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)
Below are the steps :
- Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.
- Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.
- Reverse modified linked list and return head.
Below is the implementation of above steps.
Python3
# Python3 program to add 1 to # a linked listimport sysimport math# Linked list nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to create a new node # with given data def newNode(data): return Node(data)# Function to reverse the # linked listdef reverseList(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# Adds one to a linked lists and # return the head node of # resultant listdef addOne(head): # Reverse linked list and add # one to head head = reverseList(head) k = head carry = 0 prev = None head.data += 1 # update carry for next calculation 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) # Reverse the modified list return reverseList(k)# A utility function to print # a linked listdef printList(head): if not head: return while(head): print("{}".format(head.data), end="") head = head.next# Driver codeif __name__ == '__main__': head = newNode(1) head.next = newNode(9) head.next.next = newNode(9) head.next.next.next = newNode(9) print("List is: ", end = "") printList(head) head = addOne(head) print("Resultant list is: ", end = "") printList(head)# This code is contributed by Rohit |
Output:
List is 1999 Resultant list is 2000
Time complexity: O(n)
Auxiliary Space: O(1)
Recursive Implementation:
We can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.
Below is the implementation of recursive solution.
Python
# Recursive Python program to add 1 to # a linked list# Node class class Node: # Constructor to initialize # the node object def __init__(self, data): self.data = data self.next = None# Function to create a new node # with given data def newNode(data): new_node = Node(0) new_node.data = data new_node.next = None return new_node# Recursively add 1 from end to beginning # and returns carry after all nodes are # processed.def addWithCarry(head): # If linked list is empty, then # return carry if (head == None): return 1 # Add carry returned be next node # call res = head.data + addWithCarry(head.next) # Update data and return new carry head.data = int((res) % 10) return int((res) / 10)# This function mainly uses # addWithCarry().def addOne(head): # Add 1 to linked list from end # to beginning carry = addWithCarry(head) # If there is carry after processing # all nodes, then we need to add a # new node to linked list if (carry != 0): newNode = Node(0) newNode.data = carry newNode.next = head # New node becomes head now return newNode return head# A utility function to print a # linked listdef printList(node): while (node != None): print(node.data, end = "") node = node.next print("")# Driver codehead = newNode(1)head.next = newNode(9)head.next.next = newNode(9)head.next.next.next = newNode(9)print("List is ")printList(head)head = addOne(head)print("Resultant list is ")printList(head)# This code is contributed by Arnab Kundu |
Output:
List is 1999 Resultant list is 2000
Time Complexity: O(n)
Auxiliary Space: O(n)
Please refer complete article on Add 1 to a number represented as linked list for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
