title: Linked List Concatenation
body: <p>Working on creating linked lists for an assignment and one requirement is a method named <em>concat</em> 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.</p>
  
  <p>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 <em>concat</em>. If this <strong>is</strong> 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.</p>
  
  <pre><code>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;
      }
      list1.head = concat(list1.head, tail, list1.head);
  }
  private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
      // Pass in smaller list every time
      // Head traverses down list till the end
      // Add new node with (pt's letter, null link)
      if (lhead == null) {
      // If head is null, we need to add the node
          lhead = new CharacterNode(pt.getCharacter(),null);
      } else if (tail.getNext() == lhead) {
      // If the head is past tail, stop   
      } else {
          // Call concat on a smaller list
          lhead.setNext(concat(lhead.getNext(),tail,pt));
      }
      return lhead;
  }
  </code></pre>
  
  <p>Here's CharacterNode:</p>
  
  <pre><code>class CharacterNode {
      private char letter;
      private CharacterNode next;
  
      public CharacterNode(char ch, CharacterNode link) {
          letter = ch;
          next = link;
      }
  
      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;
      }
  }
  </code></pre>
  
  <p>MyString:</p>
  
  <pre><code>class MyString {
      // member variable pointing to the head of the linked list
      private CharacterNode head;
  
      // 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
      public void addHead(char ch) {
      }
  
      // create a new node and add it to the tail of the list -- "wrapper"
      public void addTail(char ch) {
      }
  
      // Recursive method for addTail
      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) {
      }
  }
  </code></pre>