HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Linked list arithmetic

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listlinkedarithmetic

Problem

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;
publ

Solution

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;
}

Code Snippets

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;
}

Context

StackExchange Code Review Q#41090, answer score: 8

Revisions (0)

No revisions yet.