Linked Lists Java Replacing Nodes

Question

I'm having difficulty with a linked lists program. I want to write a method that destructively replaces the value in each node n by the sum of the values in the tail of the list. So if the list is 2,3,5,7; I want to change it to 17,15,12,7. I am given a program where I have to add a method that does this. I can change the first number, but I can not change the other three, and I am stuck. If anyone could help me, that would be great.

Original Program

public class IntList {
private int value;     
private IntList next;


public IntList(int v, IntList n) {          // Constructor
    value = v;
    next = n;
  }

public int getValue() { return value; }       // Getters
public IntList getNext() { return next; }
public void setValue(int v) { value = v; }    // Setters
public void setNext(IntList n) { next = n; }

// Find the last node of a linked list.
public IntList findLast() {
   if (getNext() == null) return this;
   else return getNext().findLast();
 }

// Add a new node with value v at the end of l;

public void addEnd(int v) {
    findLast().setNext(new IntList(v,null));
  }

// Add up the values in a list, recurring down the owner
public int sumList() {
   if (getNext() == null) return getValue();
   else return getValue() + getNext().sumList();
  }


// Convert list of int to string

// Recursive method for constructing the end of the string, after the
// initial open bracket.

 public String toString1() {
   if (getNext() == null)
      return getValue() + "]";
   else return getValue() + ", " + getNext().toString1();
 }

// Top level rountine that starts with the "[" and then calls toString1 to
// do the rest.

  public String toString() {
    return "[" + toString1();
  }

// Recursive method for finding the sum of a list, using recursion down
// an argument. Note that this is a static method, associated with the class
// not with an object owner.

 static public int sumListArg(IntList l) {
    if (l==null) return 0;
    else return l.getValue() + sumListArg(l.getNext());
   }

 static public void main(String[] args) {
   IntList l = new IntList(2,null);
   l.addEnd(3);
   l.addEnd(5);
   l.addEnd(7);
   System.out.println("h");
   System.out.println(l.toString());
   System.out.println("Sum = " + l.sumList());
} // end main
} // end RecursiveIntList

Here is what I have so far for my method (I think it's logically ok, but it's incorrect):

 public static void runningSum(IntList l)
{ 
     l.setValue(l.sumList());

    while(l.getNext() != null) 
     {
        l.setNext(l.getNext()); //Set Next to be the next reference
        l.getValue();  //Get the Next's value
        l.setValue(l.sumList()); //Add the rest of the numbers together
     }

     if(l.getNext() == null)
     {
         l.setValue(l.getValue());
     }

     System.out.println(l.toString());
}

gaborsch · Accepted Answer · 2013-02-11 00:57:29Z

2

There is a nice and elegant solution:

public int sumList() {
    if (getNext() == null) {
        return getValue();
    }
    value = getValue() + getNext().sumList();
    return value;
 }

In this method you recursively iterate through the List, and summarize all the elements that are behind the current element, and set the value at the same time.

edited Feb 11, 2013 at 0:57

answered Feb 11, 2013 at 0:02

gaborsch

15.8k6 gold badges41 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

damix911 Over a year ago

I believe he cannot really change the data structure.

JerryCrowley Over a year ago

I can't change the structure to a double linked list. Thank you for your help though.

gaborsch Over a year ago

How about the recursive solution?

JerryCrowley Over a year ago

That would work, but it had to be an iterative solution. Thanks for your help.

damix911 · Accepted Answer · 2013-02-11 01:00:37Z

1

This is the code:

public static void runningSum(IntList l)
{ 
    IntList head = l;
    int rSum = l.sumList();

    while(l != null) 
    {
        int curRS = rSum;
        curRS -= l.getValue();
        l.setValue(rSum);
        rSum = curRS;
        l = l.getNext();
    }

    System.out.println(head.toString());
}

I'll break it in several parts to explain what's going on. We want to code a procedure that takes the head of a list and alters the list in the way you describe; basically the first element must become the sum of all the original elements; the second element must be the sum of all elements except the first, and so on. The last element, the tail, must remain unchanged.

public static void runningSum(IntList l)
{

The function we need to remember the head that was passed to the function; we save l in a variable called head.

    IntList head = l;

The running sum for the first element is the sum of all elements; so we call sumList and store the result in a variable called rSum.

    int rSum = l.sumList();

This is a very typical idiom in data structures programming; while the element is not null, you loop.

    while(l != null) 
    {

The running sum of the next element is rSum minus the value of the current element.

        int nextRS = rSum - l.getValue();

Now we can set running sum of the current element to rSum.

        l.setValue(rSum);

For the next iteration, the current running sum is nextRS. Finally we update l to point to the next element.

        rSum = nextRS;
        l = l.getNext();
    }

If we didn't keep track of head, now we wouldn't know what to print.

    System.out.println(head.toString());
}

edited Feb 11, 2013 at 1:00

answered Feb 11, 2013 at 0:01

damix911

4,4751 gold badge34 silver badges49 bronze badges

2 Comments

JerryCrowley Over a year ago

Wow! Can you replace my professor please? lol. Thank you so much I completely understand it now.

damix911 Over a year ago

Thank you, I tried to do it by calling sumList at the beginning as you were suggesting. Didactically I think is a good example, but Code-Guru answer is the most efficient and compact, and it also has your same prototype (void function). I initially leaned to something like he did, but it was an int function so I discarded it. If you want to accept his answer I would be ok with it.

Code-Apprentice · Accepted Answer · 2013-02-11 00:13:38Z

1

Linked lists lend themselves to recursion. A recursive solution might look like this:

public static void runningSum(IntList l) {
    if (l.getNext() != null) {
        runningSum(l.getNext());
        l.setValue(l.getValue() + l.getNext().getValue());
    }
}

answered Feb 11, 2013 at 0:13

Code-Apprentice

84k26 gold badges163 silver badges290 bronze badges

Collectives™ on Stack Overflow

Linked Lists Java Replacing Nodes

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related