Add Two Numbers Represented by Linked Lists

Add Two Numbers Represented by Linked Lists

Problem Statement

Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum of the 2 numbers represented as LinkedList.

Sample Test Cases

Input 1:
firstList = 7 5 9 4 6
secondList = 8 4

Output 1: result = 5 0 0 5 6
Explanation 1:

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 -> 0 -> 0 -> 5 -> 6.

Input 2:
firstList = 0
secondList = 0
Output 2:
result = 0

Explanation 2:
Both the linked lists in the above example represent the number 0, so the result is also a single node with the value 0.

Approach

We approach this problem as follows. We will perform a traversal on both the 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 the lists, where the function recursively moves ahead on both the 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.
The algorithm is as described below:

  • 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.
  • Start a recursive function from the start nodes of both the lists, where the function will further call the next nodes of the list.
  • The recursion continues till we reach the end of a linked list.
  • 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.

C++ Code

// class Node {
// public:
//     int data;
//     Node* next;
// };
Node * addTwoLists(Node * first, Node * second) {
  Node * res = NULL;
  Node * temp;
  Node * prev = NULL;
  int carry = 0, sum = 0;
  while (first != NULL || second != NULL) {
    sum = carry;
    sum += first != NULL ? first -> data : 0;
    sum += second != NULL ? second -> data : 0;
    if (sum >= 10) {
      carry = 1;
    } else {
      carry = 0;
    }
    sum %= 10;
    temp = newNode(sum);
    if (res != NULL) {
      prev -> next = temp;
    } else {
      res = temp;
    }
    prev = temp;
    if (first) {
      first = first -> next;
    }
    if (second) {
      second = second -> next;
    }
  }

  if (carry > 0)
    temp -> next = newNode(carry);
  return res;
}

Node * reverse(Node * head) {
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  Node * rest = reverse(head -> next);
  head -> next -> next = head;
  head -> next = NULL;
  return rest;
}

Node * solve(Node * list1, Node * list2) {
  list1 = reverse(list1);
  list2 = reverse(list2);
  Node * added = addTwoLists(list1, list2);
  return added;
}

Java Code

/*
static class Node {
    int data;
    Node next;
    
    Node(int d) {
        data = d;
        next = null;
    }
}
*/
public static Node addTwoLists(Node first, Node second) {
  Node start1 = new Node(0);
  start1.next = first;
  Node start2 = new Node(0);
  start2.next = second;
  addPrecedingZeros(start1, start2);
  Node result = new Node(0);
  if (sumTwoNodes(start1.next, start2.next, result) == 1) {
    Node dummy = new Node(1);
    dummy.next = result.next;
    result.next = dummy;
  }
  return result.next;
}
public static int sumTwoNodes(Node first, Node second, Node result) {
  if (first == null) {
    return 0;
  }
  int sum = 0;
  sum += first.data;
  sum += second.data;
  sum += sumTwoNodes(first.next, second.next, result);
  Node dummy = new Node(sum % 10);
  dummy.next = result.next;
  result.next = dummy;
  return sum / 10;
}
public static void addPrecedingZeros(Node start1, Node start2) {
  Node next1 = start1.next;
  Node next2 = start2.next;
  while (next1 != null && next2 != null) {
    next1 = next1.next;
    next2 = next2.next;
  }
  if (next1 == null) {
    if (next2 != null) {
      while (next2 != null) {
        Node dummy = new Node(0);
        dummy.next = start1.next;
        start1.nedummy dummy;
        next2 = next2.next;
      }
    }
  } else if (next2 == null) {
    if (next1 != null) {
      while (next1 != null) {
        Node dummy = new Node(0);
        dummy.next = start2.next;
        start2.next = dummy;
        next1 = next1.next;
      }
    }
  }
}
public static Node solve(Node first, Node second) {
  Node result = addTwoLists(first, second);
  return result;
}

Python Code

# class Node:

#     def __init__(self, data):
#         self.data = data
#         self.next = None
def addTwoLists(self, first, second):
    prev = None
    temp = None
    carry = 0
    while first is not None or second is not None:
        if first is None:
            firstData = 0
        else:
            firstData = first.data
        if second is None:
            secondData = 0
        else:
            secondData = second.data
        Sum = carry
        Sum += firstData
        Sum += secondData
        if Sum >= 10:
            carry = 1
        else:
            carry = 0
        Sum %= 10
        temp = Node(Sum)
        if self.head is None:
            self.head = temp
        else:
            prev.next = temp
        prev = temp
        if first is not None:
            first = first.next
        if second is not None:
            second = second.next
    if carry > 0:
        temp.next = Node(carry)

Complexity Analysis

Time Complexity: O(n + m) // n = length of 1st list, m = length of 2nd list.
Space Complexity: O(n + m) // Temporary linked list needed to store results in form of dummy node.

FAQs

Q. Why are zeros appended to the end of the smaller linked list?
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’t change, but the implementation becomes easier for the problem logic.

Q. How is the carry calculated for the sum of digits?
Ans. The carry is calculated for the sum of digits as “If the sum of digits exceeds 10, the carry is 1, else it is 0.”

Additional Resources

Previous Post

Serialize and Deserialize a Binary Tree

Next Post

Data Analyst Skills You Must Have

Exit mobile version