You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

/*
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
*/

public class Solution {
  public Node add(Node l1, Node l2) {
  }
}

This problem is selected from LeetCode.

Solution

Traverse the two linked list node by node. Add up the values of each pair of nodes but be careful to the remain. Also, the two numbers may not have the same number of digits.

public class Solution {
  public Node add(Node l1, Node l2){
    if(l1==null) return l2;
    if(l2==null) return l1;

    Node head = new Node(0);
    Node p = head;

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

      p.next = new Node(tmp%10);
      p = p.next;
      tmp = tmp/10;
    }

    return head.next;
  }
}

RelatedPost