Linked Lists

Add two numbers represented using Linked Lists

Rajeev SinghAlgorithms1 mins read

Add Two Numbers problem statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3 -> 7 -> 9) + (5 -> 6 -> 8)
Output: 7 -> 0 -> 8
Explanation: 97342 + 865 = 98207.

Add Two Numbers problem solution in Java

You can add two numbers represented using LinkedLists in the same way you add two numbers by hand.

Iterate over the linked lists, add their corresponding elements, keep a carry just the way you do while adding numbers by hand, add the carry-over from the previous addition to the current sum and so on..

Here is the complete solution in Java:

class ListNode {
  int val;
  ListNode next;
  ListNode(int val) { 
    this.val = val; 
  }
}

class AddTwoNumbers {

  // O(max(l1.size, l2.size))
  private  static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = null, head = null;
    int carry = 0;

    while(l1 != null || l2 != null) {
      int sum = 0;
      if(l1 != null) {
        sum += l1.val;
        l1 = l1.next;
      }
      if(l2 != null) {
        sum += l2.val;
        l2 = l2.next;
      }
      sum += carry;

      int value  = sum%10;
      carry = sum/10;
      ListNode node = new ListNode(value);
      if(result != null) {
        result.next = node;
        result = result.next;
      } else {
        result = head = node;
      }
    }
    if(carry > 0) {
      result.next = new ListNode(carry);
    }
    return head;
  }

  public static void main(String[] args) {

    ListNode l1 = new ListNode(2);
    l1.next = new ListNode(4);
    l1.next.next = new ListNode(3);
    l1.next.next.next = new ListNode(7);
    l1.next.next.next.next = new ListNode(9);

    ListNode l2 = new ListNode(5);
    l2.next = new ListNode(6);
    l2.next.next = new ListNode(8);

    ListNode result = addTwoNumbers(l1, l2);
    while(result != null) {
      System.out.print(result.val + " ");
      result = result.next;
    }
    System.out.println();
  }
}
# Output
7 0 2 8 9