Table of Contents
DO NOT LOSE CONFIDENCE
- This is the most poorly written problem on leetcode and it is coming on number 2 which will surely destroy anyone’s confidence in the beginning.
Simple Example
Alway try to take simple example
- Number-1 : is 4321 which represented in reverse order in linked list format as [1,2,3,4]
- Number-2 : 98 which represented in reverse order in linked list format as [8,9]
SUM of number1 + number 2 = 4321 + 98 = 4419
But EXPECTED answer is NOT 4419 but it is reverse of 4419 i.e. [9, 1, 4, 4]
TRICK
- While we get the digits added to final answer 1st digit will added at head of the linked list of the answer.
- In above e.g. you can see 9 is the first digit which will always remain at the HEAD of the ANSWER.
- Now next digit will get added to tail and so on.
- So we need to update tail and keep moving tail.
- In above e.g. tail keeps updating 1, 4, 4 and so on.
JAVA CODE Add Two Numbers in Linked List format
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null, tail = null;
int carry = 0, digit = 0;
// Keep adding two digits until one of the list becomes empty
for(;(l1 != null) && (l2 != null);){
if (l2 != null) {
digit = l1.val + l2.val + carry;
}
if (digit > 9){
carry = 1;
}else{
carry = 0;
}
digit = digit % 10;
if (result == null){
result = new ListNode(digit, result);
tail = result;
}else{
tail.next = new ListNode(digit);
tail = tail.next;
}
l1 = l1.next;
l2 = l2.next;
}
ListNode remainingList = null ;
// Identify the remaining 2nd list which is non empty
if (l1 != null) {
remainingList = l1;
}else{
remainingList = l2;
}
// Process the remaining 2nd list and finish remaining operation.
for(;(remainingList != null);){
digit = remainingList.val + carry;
if (digit > 9){
carry = 1;
}else{
carry = 0;
}
digit = digit % 10;
if (result == null){
result = new ListNode(digit, result);
tail = result;
}else{
tail.next = new ListNode(digit);
tail = tail.next;
}
remainingList = remainingList.next;
}
// Always take care of last carry
if(carry == 1) {
tail.next = new ListNode(carry);
tail = tail.next;
}
return result;
}
}Visit https: https://codeandalgo.com for more such contents
Leave a Reply