{"id":27625,"date":"2018-04-04T19:36:41","date_gmt":"2018-04-04T14:06:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27625"},"modified":"2018-09-16T14:37:36","modified_gmt":"2018-09-16T09:07:36","slug":"add-1-number-represented-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/add-1-number-represented-linked-list\/","title":{"rendered":"Cpp Algorithm-Add 1 to a number represented as linked list"},"content":{"rendered":"

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)<\/p>\n

Below are the steps :<\/p>\n

    \n
  1. Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.<\/li>\n
  2. 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.<\/li>\n
  3. Reverse modified linked list and return head.<\/li>\n<\/ol>\n

    C++ prpgramming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20add%201%20to%20a%20linked%20list%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0A%20%0A%2F*%20Linked%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20reverse%20the%20linked%20list%20*%2F%0ANode%20*reverse(Node%20*head)%0A%7B%0A%20%20%20%20Node%20*%20prev%20%20%20%3D%20NULL%3B%0A%20%20%20%20Node%20*%20current%20%3D%20head%3B%0A%20%20%20%20Node%20*%20next%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20prev%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20prev%3B%0A%7D%0A%20%0A%2F*%20Adds%20one%20to%20a%20linked%20lists%20and%20return%20the%20head%0A%20%20%20node%20of%20resultant%20list%20*%2F%0ANode%20*addOneUtil(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20res%20is%20head%20node%20of%20the%20resultant%20list%0A%20%20%20%20Node*%20res%20%3D%20head%3B%0A%20%20%20%20Node%20*temp%2C%20*prev%20%3D%20NULL%3B%0A%20%0A%20%20%20%20int%20carry%20%3D%201%2C%20sum%3B%0A%20%0A%20%20%20%20while%20(head%20!%3D%20NULL)%20%2F%2Fwhile%20both%20lists%20exist%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20value%20of%20next%20digit%20in%20resultant%20list.%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20next%20digit%20is%20sum%20of%20following%20things%0A%20%20%20%20%20%20%20%20%2F%2F%20(i)%20Carry%0A%20%20%20%20%20%20%20%20%2F%2F%20(ii)%20Next%20digit%20of%20head%20list%20(if%20there%20is%20a%0A%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20next%20digit)%0A%20%20%20%20%20%20%20%20sum%20%3D%20carry%20%2B%20head-%3Edata%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20carry%20for%20next%20calulation%0A%20%20%20%20%20%20%20%20carry%20%3D%20(sum%20%3E%3D%2010)%3F%201%20%3A%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20sum%20if%20it%20is%20greater%20than%2010%0A%20%20%20%20%20%20%20%20sum%20%3D%20sum%20%25%2010%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20new%20node%20with%20sum%20as%20data%0A%20%20%20%20%20%20%20%20head-%3Edata%20%3D%20sum%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Move%20head%20and%20second%20pointers%20to%20next%20nodes%0A%20%20%20%20%20%20%20%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20if%20some%20carry%20is%20still%20there%2C%20add%20a%20new%20node%20to%0A%20%20%20%20%2F%2F%20result%20list.%0A%20%20%20%20if%20(carry%20%3E%200)%0A%20%20%20%20%20%20%20%20temp-%3Enext%20%3D%20newNode(carry)%3B%0A%20%0A%20%20%20%20%2F%2F%20return%20head%20of%20the%20resultant%20list%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20mainly%20uses%20addOneUtil().%0ANode*%20addOne(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20Reverse%20linked%20list%0A%20%20%20%20head%20%3D%20reverse(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20one%20from%20left%20to%20right%20of%20reversed%0A%20%20%20%20%2F%2F%20list%0A%20%20%20%20head%20%3D%20addOneUtil(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20Reverse%20the%20modified%20list%0A%20%20%20%20return%20reverse(head)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20linked%20list%0Avoid%20printList(Node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(1)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%0A%20%20%20%20printf(%22List%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20head%20%3D%20addOne(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnResultant%20list%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

    Output:<\/strong><\/p>\n

    List is 1999\r\n\r\nResultant list is 2000\r\n\r\n<\/pre>\n
    \u00a0Recursive Implementation:<\/strong>
    \nWe can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn\u2019t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.<\/p>\n
    C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Recursive%20C%2B%2B%20program%20to%20add%201%20to%20a%20linked%20list%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0A%20%0A%2F*%20Linked%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F%2F%20Recursively%20add%201%20from%20end%20to%20beginning%20and%20returns%0A%2F%2F%20carry%20after%20all%20nodes%20are%20processed.%0Aint%20addWithCarry(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20If%20linked%20list%20is%20empty%2C%20then%0A%20%20%20%20%2F%2F%20return%20carry%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20carry%20returned%20be%20next%20node%20call%0A%20%20%20%20int%20res%20%3D%20head-%3Edata%20%2B%20addWithCarry(head-%3Enext)%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20data%20and%20return%20new%20carry%0A%20%20%20%20head-%3Edata%20%3D%20(res)%20%25%2010%3B%0A%20%20%20%20return%20(res)%20%2F%2010%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20mainly%20uses%20addWithCarry().%0ANode*%20addOne(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20Add%201%20to%20linked%20list%20from%20end%20to%20beginning%0A%20%20%20%20int%20carry%20%3D%20addWithCarry(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20there%20is%20carry%20after%20processing%20all%20nodes%2C%0A%20%20%20%20%2F%2F%20then%20we%20need%20to%20add%20a%20new%20node%20to%20linked%20list%0A%20%20%20%20if%20(carry)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20*newNode%20%3D%20new%20Node%3B%0A%20%20%20%20%20%20%20%20newNode-%3Edata%20%3D%20carry%3B%0A%20%20%20%20%20%20%20%20newNode-%3Enext%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20return%20newNode%3B%20%2F%2F%20New%20node%20becomes%20head%20now%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20head%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20linked%20list%0Avoid%20printList(Node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(1)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%0A%20%20%20%20printf(%22List%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20head%20%3D%20addOne(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnResultant%20list%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
    Output:<\/strong><\/p>\n
    List is 1999\r\n\r\nResultant list is 2000\r\n\r\n<\/pre>\n
    \u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
    Cpp Algorithm-Add 1 to a number represented as linked list-Linked list
    \nNumber is represented in linked list such that each digit corresponds<\/p>\n","protected":false},"author":1,"featured_media":31292,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81891,81893,81885,81887,81886,81889,81888,81890,81894,81892,81884],"class_list":["post-27625","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-singly-linked-list","tag-1s-and-2s","tag-add-1-to-the-integer-represented-by-a-linked-list-with-on-time-and-o1-space","tag-add-2-linked-lists","tag-add-one-to-number-array","tag-add-two-linked-lists-c","tag-find-next-greater-element-with-same-digits","tag-get-a-number","tag-given-a-linked-list-of-0s","tag-how-to-find-if-words-in-a-file-are-anagram","tag-sort-it","tag-sum-of-two-linked-lists-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27625","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27625"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27625\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31292"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27625"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27625"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27625"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}