Question:

How to Add two numbers represented by linked lists?

Summary:

Suppose we have two decimal numbers represented by two linked lists of size N and M respectively.

We have to return a linked list that represents the sum of these two numbers.

For example, the number 190 will be represented by the linked list, 1->9->0->null, similarly 25 by 2->5->null. Sum of these two numbers is 190 + 25 = 215, which will be represented by 2->1->5->null. You are required to return the head of the linked list 2->1->5->null.

Solution:

/* node for linked list

class Node {

int data;

Node next;

Node(int d) {

data = d;

next = null;

}

class Solution{

//Function to add two numbers represented by linked list.

static Node addTwoLists(Node first, Node second){

// code here

// return head of sum list

first = reverseList(first);

second = reverseList(second);

Node res = null, cur1 = first, cur2 = second, cur = null;

int carry = 0;

while (cur1 != null && cur2 != null) {

int sum = cur1.data + cur2.data + carry;

Node n = new Node(sum % 10);

carry = sum / 10;

if (res == null) {

res = cur = n;

}

else {

cur.next = n;

cur = cur.next;

}

cur1 = cur1.next;

cur2 = cur2.next;

}

while (cur1 != null) {

int sum = cur1.data + carry;

Node n = new Node(sum % 10);

carry = sum / 10;

cur.next = n;

cur = cur.next;

cur1 = cur1.next;

}

while (cur2 != null) {

int sum = cur2.data + carry;

Node n = new Node(sum % 10);

carry = sum / 10;

cur.next = n;

cur = cur.next;

cur2 = cur2.next;

}

if (carry > 0) {

Node n = new Node(carry);

cur.next = n;

}

return reverseList(res);

}

static Node reverseList(Node head) {

if (head.next == null) return head;

Node temp = head.next;

Node newHead = reverseList(temp);

temp.next = head;

head.next = null;

return newHead;

}

Explanation:

The method addTwoLists takes two parameters, first and second, which represent the heads of two linked lists containing digits of the numbers to be added.
It first reverses both input linked lists using the reverseList method, which recursively reverses a linked list.
Then, it traverses both lists simultaneously, summing corresponding digits along with any carry from the previous addition.
It creates a new node with the sum of digits (modulo 10) and updates the carry for the next iteration.
It constructs a result linked list by appending nodes with the calculated sum.
If there's any remaining carry after the traversal, it adds a new node with the carry to the end of the result linked list.
Finally, it returns the reversed result linked list.
Additionally, there's a helper method reverseList to reverse a given linked list recursively.