[FIXED] How do I recursively append two linked lists in Java?

Issue

So basically my code iterates through the list and the original method is supposed to return the linked list however it doesn't seem to be adding the nodes that I link in the recursive method and I'm confused as to why. Can anyone help me?

    // Append MyStringBuilder2 b to the end of the current MyStringBuilder2, and
    // return the current MyStringBuilder2.  Be careful for special cases!
    public MyStringBuilder2 append(MyStringBuilder2 b)
    {
        //Test if Invalid
        if(b.firstC==null){
            
            return this;
        }
        //Test if condition is met
        else {
            CNode lastNode =firstC;
            recurseAppendBuild(lastNode, b);
            
            return this;
            
        }
    }
    private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
        //Test if all nodes have been added
        if(lastNode.next==null&&BPoint.firstC==null) {
            System.out.println("finished");
        }
        //Tests if all nodes in the original linked list have been passed through
        else if(lastNode.next==null) {
            
            lastNode.next= new CNode(BPoint.firstC.data);
            BPoint.firstC=BPoint.firstC.next;
            recurseAppendBuild(lastNode.next, BPoint);
        }
        //Recurse until condition is met
        else {
            
            recurseAppendBuild(lastNode.next, BPoint);
        }
    }
    ```

Solution

Okay, your code needs some work. Let's look at your first method. I'm going to rewrite it.

public MyStringBuilder2 append(MyStringBuilder2 fromBuilder)
{
    if (fromBuilder.firstC != null) {
        recurseAppendBuild(fromBuilder.firstC);
    }

    return this;
}

I changed a number of things.

1. I used a more meaningful name on the argument. It's a good idea to give your variables meaningful names, not just 'b'. Note that I never use one-character names. If nothing else, it can be really hard to search on that. If you do "int i" and then search for i, you'll get a LOT of hits that aren't i at all.

This is a very trivial thing and doesn't affect the quality of your code.

2. In all cases, you always return yourself, so the return statement can be after the if-else structure, which is easier to see that it's the same.

3. That eliminates the top if-block entirely, so I reversed the logic.

4. And I changed the method signature of your recursive method, for reasons I'll describe below.

The end result is short and sweet and easily understood.

---

Now, let's look at your second method:

private void recurseAppendBuild(CNode lastNode, MyStringBuilder2 BPoint) {
    //Test if all nodes have been added
    if(lastNode.next==null&&BPoint.firstC==null) {
        System.out.println("finished");
    }
    //Tests if all nodes in the original linked list have been passed through
    else if(lastNode.next==null) {
        
        lastNode.next= new CNode(BPoint.firstC.data);
        BPoint.firstC=BPoint.firstC.next;
        recurseAppendBuild(lastNode.next, BPoint);
    }
    //Recurse until condition is met
    else {
        
        recurseAppendBuild(lastNode.next, BPoint);
    }
}

1. Your variable named BPoint breaks JAVA naming standards. It should start with a lower case letter.

2. If you pass in a MyStringBuilder2 as the second argument, then as you move things from BPoint to the end of your list and recurse, you have to remove them from BPoint, which is a pain in the ass. So instead, I didn't point to the wrapper. In my code above, I passed in the head of the list (fromBuilder.firstC).

3. You are finished when your list-to-append-from (BPoint) is empty, not when lastNode is null. Your first if is flawed.

4. You aren't recursively adding items. You're recursively looking for the end of the list. I don't think that's what you really want.

5. You're messing up the integrity of BPoint. You're making a copy of the nodes as you add them, but you're then dropping the old ones from BPoint but NOT maintaining lastC at all.

6. And you have a significant problem if your list starts as empty, as firstC and lastNode will both be empty.

---

So let's think about it this way. First, doing this recursively is silly, but that's the assignment, so we'll work with it.

A recursive definition is:

AppendedList = OriginalList + firstItem + Append Tail of List.

private void recurseAppendBuild(CNode headToAppend) { if (headToAppend == NULL) { // All done. return; }

   CNode nodeToAppend = new CNode(headToAppend.data);
   if (lastC == nullptr) {
       // Original list is empty.
       firstC = lastC = nodeToAppend;
   else {
       lastC.next = nodeToAppend;
       lastC = nodeToAppend;  // Point the tail at the new tail
   }

   // And here you recurse, always.
   recurseAppendBuild(headToAppend.next);

}

Let's look at this.

1. I'm assuming you keep both a firstC and lastC in your builder. It would be deeply inefficient otherwise. So you only need to pass in the chain of nodes, not the surrounding wrapper.

2. By putting a null-check at the top of this method, you eliminate other null checks. Note -- this means we can eliminate the null check in the first method.

3. Create the new copy right away. That part's easy, right?

4. If lastC is null, you have an empty list, so you just point both front and back of the list to your new node.

5. Otherwise you point the old tail's next pointer to your new node and update the tail pointer to remain pointed at the tail.

6. Either way, you can safely recurse with the next object in the original list.

Advantages of this method, aside from working, is that you don't destroy the original list, and it's pretty clear to read.

Answered By - Joseph Larson

Answer Checked By - Candace Johnson (PHPFixing Volunteer)