Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am practicing for interviews and I tried solving the problem on my own and got a solution. I was wondering how can I improve the performance and memory on this program?

The problem performs addition on linked list nodes. The nodes are 1s->10s->100s->.... The goal of this program is to perform addition on two of these linked lists. The output should be a linked list of the same format.

Example:

  1 -> 4 -> 3 
+ 1 -> 5 -> 9 -> 2 

Linked list output:

2 -> 9 -> 2 -> 3

Here is my code:

public class prob2_5 {
    /*
     * You have two numbers represented by a linked list, where each node contains a single digit.
     * The digits are stored in reverse order, such that the 1's digit is at the head of the list.
     * Write a function that adds the two numbers and returns the sum as a linked list
     * 
     */

    public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
        int l1sum = 0;
        int l2sum = 0;
        int multiplier = 1;

        while(l1 != null) {
            l1sum = l1sum + l1.value*multiplier;
            multiplier = multiplier*10;
            l1 = l1.next;
        }
        multiplier = 1;
        while(l2 != null) {
            l2sum = l2sum + l2.value*multiplier;
            multiplier = multiplier*10;
            l2 = l2.next;
        }

        int total = l2sum + l1sum;

        char[] totalnum = (total + "").toCharArray();
        int len = totalnum.length;
        LinkedListNode tail = new LinkedListNode(totalnum[len - 1] - '0');
        LinkedListNode newNode;
        LinkedListNode prevNode = tail;
        System.out.print(totalnum);

        for (int i = len - 2; i >= 0; i--) {            
            newNode = new LinkedListNode(totalnum[i] - '0');
            prevNode.next = newNode;        
            prevNode = newNode; 
        }
        return tail;
    }   
}

Here is my linked list class:

public class LinkedListNode {
    LinkedListNode next;
    int value;
    public LinkedListNode(int value) {
        this.next = null;
        this.value = value;
    }
}
share|improve this question
    
What is your LinkedListNode implementation? Could you provide a runnable example? I didn't really understand your explanation completely. –  Simon André Forsberg Feb 6 at 18:25
    
Sorry Ill add more to my post –  Liondancer Feb 6 at 18:34
1  
OK, now I understand. 143 really represents the number 341, and 1592 is 2951. 2951 + 341 = 3292, which is 2923 backwards. –  Simon André Forsberg Feb 6 at 18:38
    
yes exactly! =D –  Liondancer Feb 6 at 18:48

2 Answers 2

up vote 8 down vote accepted

I believe you are missing the point of the exercise - instead of 'decoding' the input numbers, and then 're-encoding' the output number - you are supposed to iteratively get to the answer by going over the nodes of both lists:

public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
  return addLists(0, l1, l2);
}

private static LinkedListNode addLists(int carryOver, LinkedListNode l1, LinkedListNode l2) {
  // stop conditions
  if (l1 == null && l2 == null && carryOver == 0) {
    return null;
  }
  if (l1 == null) {
    l1 = new LinkedListNode(0);
  }
  if (l2 == null) {
    l2 = new LinkedListNode(0);
  }

  // iteration
  int addedValue = l1.value + l2.value + carryOver;
  carryOver = 0;

  if (addedValue >= 10) {
    addedValue -= 10;
    carryOver = 1;
  }

  l3 = new LinkedListNode(addedValue);

  // recursion
  l3.next = addLists(carryOver, l1.next, l2.next);

  return l3;
}
share|improve this answer
3  
Instead of l1 = new LinkedListNode(0), I'd suggest creating a null object: private static final NULL_NODE = new LinkedListNode(0); –  200_success Feb 6 at 19:58

Uri has a good answer, this answer is just to add a second spin on the problem....

Recursion is a good tool to have, but it is not necessarily the best tool for all occasions. In this instance, it's a toss-up.... but the iterative solution to this problem is perhaps a simpler thing to read..... and should be considered. Additionally, in many cases an iterative solution will outperform a recursive solution. In this case, again, it is a toss-up because the lists will be so short.... but, if the list was long, the recursive approach will fail with a stack-overflow... the iterative approach will keep trucking though.

public static final LinkedListNode add(LinkedListNode a, LinkedListNode b) {
    // this pointer points to the result, it is not the actual result.
    final LinkedListNode pointer = new LinkedListNode(0);

    int carry = 0;
    LinkedListNode cursor = pointer;
    while (a != null || b != null) {
        int digitsum = carry;
        if (a != null) {
            digitsum += a.value;
            a = a.next;
        }
        if (b != null) {
            digitsum += b.value;
            b = b.next;
        }
        cursor.next = new LinkedListNode(digitsum % 10);
        carry = digitsum / 10;
        cursor = cursor.next;
    }
    if (carry != 0) {
        cursor.next = new LinkedListNode(carry);
    }

    // don't return the dummy pointer, return the actual result
    return pointer.next;
}

Some side-notes:

  • the variables l1 and l2 are not great names....
  • The LinkedListNode should probably have a final value, and there should be getters for the value and next, and a setter for the next.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.