Working on creating linked lists for an assignment and one requirement is a method named concat which takes a list parameter and appends it to the end of the current list. It’s not necessary for this method to use recursion, but our programs are supposed to use recursion heavily. I’m just wondering if it’s even possible to come up with a recursive algorithm for this. Our list classes only have a head node, nothing else, and they’re not doubly linked.

My current attempt can only append the first value recursively. I know what it’s doing wrong, but I can’t come up with a solution. The first method is what’s actually called on a list with a list being passed in to “concatenate”. I then attempt to find the tail of the list and pass these in to the recursive method. This “wrapper” method is a mandatory requirement for our recursive methods. Here’s my attempt, but it’s obviously failing since I’m having trouble advancing the node reference “pt” to the next node in the list once all of the calls pop off the stack and then re-entering recursive calls to concat. If this is possible with recursion, can you please give me an idea of how to advance this value down the first list and re-enter the recursive calls or maybe just a better general approach towards this problem? Thanks for your time.

```public void concat(MyString list1) {
CharacterNode tail = null, pt = list1.head;
// Find the tail of the list
if (pt == null) {
} else if (pt.getNext() == null) {
tail = pt;
} else {
while (pt.getNext() != null) {
pt = pt.getNext();
}
tail = pt;
}
}
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
// Pass in smaller list every time
// Head traverses down list till the end
} else if (tail.getNext() == lhead) {
// If the head is past tail, stop
} else {
// Call concat on a smaller list
}
}
```

Here’s CharacterNode:

```class CharacterNode {
private char letter;
private CharacterNode next;

public CharacterNode(char ch, CharacterNode link) {
letter = ch;
}

public void setCharacter(char ch) {
this.letter = ch;
}

public char getCharacter() {
return letter;
}

public void setNext(CharacterNode next) {
this.next = next;
}

public CharacterNode getNext() {
return next;
}
}
```

MyString:

```class MyString {

// default constructor
public MyString() {
}

// copy constructor
public MyString(MyString l) {
}

// constructor from a String
public MyString(String s) {
}

// for output purposes -- override Object version
// no spaces between the characters, no line feeds/returns
public String toString() {
}

// create a new node and add it to the head of the list
}

// create a new node and add it to the tail of the list -- "wrapper"
}

private static CharacterNode addTail(CharacterNode L, char letter) {
}

// modify the list so it is reversed
public void reverse() {
}

// remove all occurrences of the character from the list -- "wrapper"
public void removeChar(char ch) {
}

// Recursive removeChar method
private static CharacterNode removeChar(CharacterNode n, char letter) {
}

// "wrapper" for recursive length()
public int length() {
}

// Returns the length of the linked list
private static int length(CharacterNode L) {
}

// concatenate a copy of list1 to the end of the list
public void concat(MyString list1) {
}

// recursive method for concat
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
}
}
```

```Node first_list = ...  // head node
Now concentrate on implementing `getLastNode()`. It can be done very simply by using either recursion or iteration, literally in 2 lines.