Adding two linked lists

I started refactoring the addTwoLinkedLists with some crazy ideas like returning fast if one of the arguments was null, or later on if the carry is 0 and one of the lists is null (in those cases you can just add the non-empty list to the result and return the resulting list).

But I kept duplicating code to handle the separate cases without really improving the readability. So I started over and just tried to rename and restructure your current implementation a bit instead to see how readable that becomes. The result looks like this:

public static Node addTwoLinkedLists(Node head1, Node head2) {
    /*ALGORITHM:
    1. Create a resultant list and move the tail pointer whenever add a node
    2. Loop the linkedLists while anyone exists
    3. calculate the sum of two nodes: If node does not exist in any of the linkedlist-> add zero for that node
           if sum of two nodes > 10, carry = 1 : else carry = 0;
    4. create a temporary node with data = sum and append it it to resultant list
    5. increment pointers of linkedlist1 and linkedlist2 (if they are not null)
    */
    Node resultantList = null;
    Node previousNode = null;
    int carry = 0;

    while( (head1 != null) || (head2 != null) ) {
        int sum = carry;
        if(head1 != null){
            sum += head1.data;
        }
        if(head2 != null) {
            sum += head2.data;
        }

        carry = sum / 10;
        Node currentNode = new Node(sum % 10);

        if (resultantList == null ) {
            resultantList = currentNode;
            previousNode = currentNode;
        } else  {
            previousNode.next = currentNode;
            previousNode = previousNode.next;
        }

        if ( head1 != null ) {
            head1 = head1.next;
        }
        if ( head2 != null ) {
            head2 = head2.next;
        }
    }

    if(carry > 0) {
        previousNode.next = new Node(carry);
    }

    return resultantList;
}

The most notable changes here are:

• putting the headX = headX.next handling at the end of the loop.
• renaming temp to currentNode and tail to previousNode to fit better with what they actually are.
• removed the `dataFromXLinkedList variables in favor of directly adding it to the sum.
• Inlined your sum variable in the temp node creation.
• put redundand tail=temp inside the else (as opposed to removing it from the if statement) and changed it to tail = tail.next to better show what's happening.
• removed redundant comments. If you need a comment to tell what the code does it's usually a sign that you want to rename things.

I also fixed a bug that you ignored the carry if both lists are empty. For examle if you have the list {8} and {9} you want the result {7,1} but got {7}.

This actually looks good enough to me :)

Next is the printList method. Having to create an instance of the class just to call this method seems wrong to me. It should be static just like the addTwoLinkedLists method. I also noticed that you call that last one on an instance. But I'll come back to that after rewriting the printList method.

After refactoring most of the previous method I finally understood that the "lists" are actualy linked list representations of numbers. So when you want to print such a number, the most natural way would be from the most significant to the least. I would write this like so:

/* Utility function to print a linked list */
public static void printList(Node head) {
    StringBuilder result = new StringBuilder();
    while (head != null) {
        result.append(head.data);
        head = head.next;
    }
    System.out.println(result.toString());
}

Next I'm wondering how you intend to use this class. You have an internal static class Node that can only be accessed inside the package of this class. This doesn't really make sense, since that means we can access the AddTwoLinkedLists class from outside the package, but can't do anything with it. So let's at least make the Node class public as well.

There are also 2 Node fields inside the class. I see absolutely no reason why these exist. You use them in your main method, and even overwrite the exact same variables for the second test case. So I guess you don't know what static means.

Here is a main method that does exactly the same thing as yours did, but without instantiating the class:

public static void main(String[] args) {
    Node head1;
    Node head2;

    // creating first list for testCase 1
    head1 = new Node(7);
    head1.next = new Node(5);
    head1.next.next = new Node(9);
    head1.next.next.next = new Node(4);
    head1.next.next.next.next = new Node(6);
    System.out.print("First List is ");
    AddTwoLinkedLists.printList(head1);

    // creating seconnd list
    head2 = new Node(8);
    head2.next = new Node(4);
    System.out.print("Second List is ");
    AddTwoLinkedLists.printList(head2);

    // add the two lists and see the result
    Node rs1 = addTwoLinkedLists(head1, head2);
    System.out.print("Resultant List is ");
    AddTwoLinkedLists.printList(rs1);

    // creating first list for testCase 1
    head1 = new Node(5);
    head1.next = new Node(6);
    head1.next.next = new Node(3);
    System.out.print("First List is ");
    AddTwoLinkedLists.printList(head1);

    // creating seconnd list
    head2 = new Node(8);
    head2.next = new Node(4);
    head2 = new Node(2);
    System.out.print("Second List is ");
    AddTwoLinkedLists.printList(head2);

    // add the two lists and see the result
    Node rs2 = addTwoLinkedLists(head1, head2);
    System.out.print("Resultant List is ");
    AddTwoLinkedLists.printList(rs2);
}

Notice how the head1 and head2 variables are re-used for both tests? You also did this since they were static. Calling testCase1.head1 is exactly the same as calling AddTwoLinkedLists.head1. You never needed that instance in the first place.

If we now look at the class it becomes clear that it's actually a collection of utility functions. So let's make this perfectly clear in the code as well like so:

public class LinkedListNumberUtils {

    private LinkedListNumberUtils(){}

I renamed the class to point out that it's a collection of utility functions that work on some LinkedListNumber. And I added a private constructor so that nobody can instantiate an instance of this class (they shouldn't do so in the first place).

Now that I showed you how your solution could look like with some basic restructuring I'll also show a completely different approach. Here's what happens if you make the Node class do most of the work:

public static class Node implements Cloneable {
    public int data;
    public Node next = null;

    /**
     * data should be a number between 0 and 9.
     * To create a new Node from a higher number use createNode(int number) instead.
     */
    public Node(int data){
        this.data = data;
    }

    public static Node createNode(int number){
        Node result = new Node(0);
        result.add(number);
        return result;
    }

    public void add(int d){
        int sum = d+data;
        int carry = sum/10;
        data = sum%10;
        if(carry > 0){
            if(next == null){
                next = new Node(carry);
            } else {
                next.add(carry);
            }
        }
    }

    @Override
    public Node clone(){
        Node result = new Node(data);
        Node head = next;
        Node current = result;
        while(head != null){
            current.next = head;
            current = current.next;
            head = head.next;
        }
        return result;
    }

    @Override
    public String toString(){
        StringBuilder result = new StringBuilder(Integer.toString(data));
        Node head = next;
        while(head != null){
            result.insert(0,head.data);
            head = head.next;
        }
        return result.toString();
    }
}

public static Node add(Node head1, Node head2){
    if(head1 == null){
        if(head2 == null) {
            return new Node(0); // nicer to return the number 0 instead of null
        }
        return head2.clone();
    }
    if(head2 == null){
        return head1.clone();
    }

    Node result = head1.clone();
    Node previousNode = result;
    previousNode.add(head2.data);
    head2 = head2.next;

    while(previousNode.next != null && head2 != null){
        previousNode = previousNode.next;
        previousNode.add(head2.data);
        head2 = head2.next;
    }
    if(head2 != null){
        previousNode.next = head2.clone();
    }
    return result;
}

Important note here is that I never used recursion. That way we can use our program for large numbers as well without being afraid of a stackoverflow. Take this for example:

public static void main(String[] args) {
    Node head2 = Node.createNode(Integer.MAX_VALUE);
    System.out.println(head2);
    Node head1 = Node.createNode(Integer.MAX_VALUE);
    System.out.println(head1);
    System.out.println(LinkedListNumberUtils.add(head1, head2));
}

It also shows what makes this linked list representation so useful. Namely that we can represent really large numbers as well (although this implementation isn't really that great memory wise, with all those ints for each digit).