Input: <\/strong>LinkedList: 4->5->6
Output: <\/strong>457
Explanation:<\/strong> 4->5->6 represents 456 and when 1 is added it becomes 457. <\/pre>\n\n\n\nInput: <\/strong>LinkedList: 1->2->3\nOutput: <\/strong>124![](\"https:\/\/media.geeksforgeeks.org\/img-practice\/prod\/addEditProblem\/700053\/Web\/Other\/blobid1_1722278908.png\")
Explanation:<\/strong> 1->2->3 represents 123 and when 1 is added it becomes 124. <\/pre>\n\n\n\nExpected Time Complexity: <\/strong>O(n)
Expected Auxiliary Space: <\/strong>O(1)<\/p>\n\n\n\nConstraints:<\/strong>
1 <= len(list) <= 105
<\/sup>0 <= list[i] <= 9<\/p>\n\n\n\n\t\t\t\n\t\t\t\tContents:<\/div>\n\t\t\t\t\n\t\t\t\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\n\t\t\t\t
- Solution: Optimal Approach (Reverse and Add)<\/a>
- Intuition<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Code<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Simplifying It<\/a><\/li><\/ul><\/li>
- Alternative Approach (Without Reversing)<\/a><\/li>
- Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n
\n\n\n\nSolution: Optimal Approach (Reverse and Add)<\/h2>\n\n\n\n
Intuition<\/h3>\n\n\n\n
Think of this like adding 1 to a number written on paper! When we add 1 to a number, we start from the rightmost digit (least significant). If that digit is 9, it becomes 0 and we carry 1 to the next digit. We keep doing this until we don’t have a carry anymore. Since our linked list starts from the leftmost digit, we need to reverse it first, do our addition, and then reverse it back!<\/p>\n\n\n\n
Detailed Approach<\/h3>\n\n\n\n
\n
- Reverse the List<\/strong>: Since we need to add from the least significant digit, reverse the entire linked list<\/li>\n\n\n\n
- Add One<\/strong>: Start from the new head (which was the last digit originally) and add 1<\/li>\n\n\n\n
- Handle Carry<\/strong>: If the current digit is 9, it becomes 0 and we carry 1 to the next digit<\/li>\n\n\n\n
- Continue with Carry<\/strong>: Keep propagating the carry until we find a digit that’s not 9<\/li>\n\n\n\n
- Handle New Digit<\/strong>: If we reach the end with a carry, create a new node with value 1<\/li>\n\n\n\n
- Reverse Back<\/strong>: Reverse the list again to restore the original order<\/li>\n<\/ol>\n\n\n\n
Code<\/h3>\n\n\n\n
![](\"https:\/\/media.geeksforgeeks.org\/img-practice\/prod\/addEditProblem\/700053\/Web\/Other\/blobid0_1722278845.png\")