{"id":5054,"date":"2023-02-14T16:03:27","date_gmt":"2023-02-14T10:33:27","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=5054"},"modified":"2023-02-14T16:03:28","modified_gmt":"2023-02-14T10:33:28","slug":"add-two-numbers-represented-by-linked-lists","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/add-two-numbers-represented-by-linked-lists\/","title":{"rendered":"Add Two Numbers Represented by Linked Lists"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#add-two-numbers---solve-problem--\">Add Two Numbers: <strong>Solve Problem<\/strong><\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum of the 2 numbers represented as LinkedList. <\/p>\n\n\n\n<p id=\"sample-test-cases\"><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<ul><li><strong>Input 1:<\/strong><ul><li>firstList = 7 5 9 4 6<\/li><li>secondList = 8 4<\/li><\/ul><\/li><li><strong>Output 1:<\/strong> <ul><li>Result = 5 0 0 5 6<\/li><\/ul><\/li><\/ul>\n\n\n\n<p><strong>Explanation 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"258\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5115 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-1024x258.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-1024x258.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-300x76.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-768x193.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-1536x387.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-2048x516.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-380x96.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-550x139.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-800x201.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7-1160x292.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-7.png 2958w\" ><\/figure>\n\n\n\n<p>Adding the linked lists in the above manner with the rules of sum and carry of addition, we get the resultant linked-list as 5 -&gt; 0 -&gt; 0 -&gt; 5 -&gt; 6.<\/p>\n\n\n\n<ul><li><strong>Input 2:<\/strong><ul><li>firstList = 0<\/li><li>secondList = 0<\/li><\/ul><\/li><li><strong>Output 2:<\/strong><ul><li>Result = 0<\/li><\/ul><\/li><\/ul>\n\n\n\n<p><strong>Explanation 2:<\/strong><br>Both the linked lists in the above example represent the number 0, so the result is also a single node with the value 0.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<p>We approach this problem as follows. We will perform a traversal on both lists and append zeros on the list which has a lesser number of digits till both numbers have an equal number of digits. Then we can recursively start from the start nodes of both lists, where the function recursively moves ahead on both lists till we reach the end. In the process of recursion, we will keep creating new nodes which will store the sum of the digits, and the recursive function returns the carry onto the next node for the sum operation.<br><\/p>\n\n\n\n<p>The algorithm is as described below:<\/p>\n\n\n\n<ul><li>Perform a traversal on both the linked lists and make the shorter list of length equal to the long list by appending zeros to its end.<\/li><li>Start a recursive function from the start nodes of both lists, where the function will further call the next nodes of the list.<\/li><li>The recursion continues till we reach the end of a linked list.<\/li><li>While continuing our recursion, we will keep adding new nodes which will store the sum of digits of our result, and the recursive function will return the carry to the next step in each recursive call.<\/li><\/ul>\n\n\n\n<h3 id=\"add-two-numbers---solve-problem--\"><span id=\"add-two-numbers-solve-problem\">Add Two Numbers: <strong><a href=\"https:\/\/www.interviewbit.com\/problems\/add-two-numbers-as-lists\/\" target=\"_blank\" rel=\"noreferrer noopener\">Solve Problem<\/a><\/strong><\/span><\/h3>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ class Node {\n\/\/ public:\n\/\/     int data;\n\/\/     Node* next;\n\/\/ };\nNode * addTwoLists(Node * first, Node * second) {\n  Node * res = NULL;\n  Node * temp;\n  Node * prev = NULL;\n  int carry = 0, sum = 0;\n  while (first != NULL || second != NULL) {\n    sum = carry;\n    sum += first != NULL ? first -> data : 0;\n    sum += second != NULL ? second -> data : 0;\n    if (sum >= 10) {\n      carry = 1;\n    } else {\n      carry = 0;\n    }\n    sum %= 10;\n    temp = newNode(sum);\n    if (res != NULL) {\n      prev -> next = temp;\n    } else {\n      res = temp;\n    }\n    prev = temp;\n    if (first) {\n      first = first -> next;\n    }\n    if (second) {\n      second = second -> next;\n    }\n  }\n\n  if (carry > 0)\n    temp -> next = newNode(carry);\n  return res;\n}\n\nNode * reverse(Node * head) {\n  if (head == NULL || head -> next == NULL) {\n    return head;\n  }\n  Node * rest = reverse(head -> next);\n  head -> next -> next = head;\n  head -> next = NULL;\n  return rest;\n}\n\nNode * solve(Node * list1, Node * list2) {\n  list1 = reverse(list1);\n  list2 = reverse(list2);\n  Node * added = addTwoLists(list1, list2);\n  return added;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*\nstatic class Node {\n    int data;\n    Node next;\n    \n    Node(int d) {\n        data = d;\n        next = null;\n    }\n}\n*\/\npublic static Node addTwoLists(Node first, Node second) {\n  Node start1 = new Node(0);\n  start1.next = first;\n  Node start2 = new Node(0);\n  start2.next = second;\n  addPrecedingZeros(start1, start2);\n  Node result = new Node(0);\n  if (sumTwoNodes(start1.next, start2.next, result) == 1) {\n    Node dummy = new Node(1);\n    dummy.next = result.next;\n    result.next = dummy;\n  }\n  return result.next;\n}\npublic static int sumTwoNodes(Node first, Node second, Node result) {\n  if (first == null) {\n    return 0;\n  }\n  int sum = 0;\n  sum += first.data;\n  sum += second.data;\n  sum += sumTwoNodes(first.next, second.next, result);\n  Node dummy = new Node(sum % 10);\n  dummy.next = result.next;\n  result.next = dummy;\n  return sum \/ 10;\n}\npublic static void addPrecedingZeros(Node start1, Node start2) {\n  Node next1 = start1.next;\n  Node next2 = start2.next;\n  while (next1 != null &amp;&amp; next2 != null) {\n    next1 = next1.next;\n    next2 = next2.next;\n  }\n  if (next1 == null) {\n    if (next2 != null) {\n      while (next2 != null) {\n        Node dummy = new Node(0);\n        dummy.next = start1.next;\n        start1.nedummy dummy;\n        next2 = next2.next;\n      }\n    }\n  } else if (next2 == null) {\n    if (next1 != null) {\n      while (next1 != null) {\n        Node dummy = new Node(0);\n        dummy.next = start2.next;\n        start2.next = dummy;\n        next1 = next1.next;\n      }\n    }\n  }\n}\npublic static Node solve(Node first, Node second) {\n  Node result = addTwoLists(first, second);\n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># class Node:\n\n#     def __init__(self, data):\n#         self.data = data\n#         self.next = None\ndef addTwoLists(self, first, second):\n    prev = None\n    temp = None\n    carry = 0\n    while first is not None or second is not None:\n        if first is None:\n            firstData = 0\n        else:\n            firstData = first.data\n        if second is None:\n            secondData = 0\n        else:\n            secondData = second.data\n        Sum = carry\n        Sum += firstData\n        Sum += secondData\n        if Sum >= 10:\n            carry = 1\n        else:\n            carry = 0\n        Sum %= 10\n        temp = Node(Sum)\n        if self.head is None:\n            self.head = temp\n        else:\n            prev.next = temp\n        prev = temp\n        if first is not None:\n            first = first.next\n        if second is not None:\n            second = second.next\n    if carry > 0:\n        temp.next = Node(carry)<\/pre>\n\n\n\n<p id=\"complexity-analysis\"><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n + m) \/\/ n = length of 1st list, m = length of 2nd list.<\/li><li><strong>Space Complexity:<\/strong> O(n + m) \/\/ Temporary linked list needed to store results in form of dummy node.<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. Why are zeros appended to the end of the smaller linked list?<\/strong><br>Ans. Zeroes are appended to the end of the linked list which is equivalent to adding zeros before a number, the value the list represents doesn\u2019t change, but the implementation becomes easier for the problem logic.<\/p>\n\n\n\n<p><strong>Q. How is the carry calculated for the sum of digits?<\/strong><br>Ans. The carry is calculated for the sum of digits as \u201cIf the sum of digits exceeds 10, the carry is 1, else it is 0.\u201d<\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/\" target=\"_blank\">Detect Loop in Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/reverse-a-linked-list\/\" target=\"_blank\">Reverse a Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/delete-node-in-a-linked-list\/\" target=\"_blank\">Delete Node in a Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/intersection-of-two-linked-lists\/\" target=\"_blank\">Intersection of Two Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-interview-questions\/\" target=\"_blank\">Linked List Interview Questions<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-mcq\/\" target=\"_blank\">Linked List MCQ<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/application-of-linked-list\/\" target=\"_blank\">Application of Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/types-of-linked-list\/\" target=\"_blank\">Types of Linked List<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum&hellip;\n","protected":false},"author":5,"featured_media":5116,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[688,392],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5054"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=5054"}],"version-history":[{"count":32,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5054\/revisions"}],"predecessor-version":[{"id":16270,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5054\/revisions\/16270"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5116"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=5054"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=5054"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=5054"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}