Recursive Reversal of Linked List in Java

[banana1073]

For my Computer Science class, we are writing several different methods to reverse a singly linked list in Java. I cannot figure out the last way, which uses three helper methods, pointerToLast(Node n) which returns the tail node, nextToLast(Node n) which returns the second to last, and append(Node a, Node b) which links together the two nodes. The method is supposed to be recursive. Here's what I have so far:

public static ListNode reverse(ListNode head)
      {
         if(head == null)
            return null;
         if(head.getNext() == null)
            return head;
         ListNode r = pointerToLast(head);
         nextToLast(head).setNext(null);
         append(r, reverseLL(head));
         return r;
      }

I was trying to make head shorter and keep adding the last value, which didn't work.
Oh, I forgot to mention that we have our own ListNode class, which only has next and value as private data, getNext() and getValue() for accessors, and setNext() and setValue() for modifiers. So anything like "a.previous" doesn't help. I'm really confused, can anyone help me? I can't figure out the recursion, like how to add stuff on.

[Taywin]

If you are going to do this in recursive way, it sounds like a way to do with scheme (functional language) using CDR. :P Anyway, the idea to do this is...
1)Keep traverse through the list until you hit the last node
2)Return the last node back to the caller
3)In the caller, use the last node and append it from the current node you found.

/*
head <- a linked list head pointer
reverse (head)
  if head is null
    return null
  else if head.getNext() is null
    return head
  else
    tmpNode <- head.getNext()
    reset head.next to null
    return append(reverse(tmpNode), head)
*/

I assume that append() means append whatever the 2nd argument to the first argument. Not sure if this algorithm works at the moment. No program to test.

[banana1073]

If you are going to do this in recursive way, it sounds like a way to do with scheme (functional language) using CDR. :P Anyway, the idea to do this is...
1)Keep traverse through the list until you hit the last node
2)Return the last node back to the caller
3)In the caller, use the last node and append it from the current node you found.

/*
head <- a linked list head pointer
reverse (head)
  if head is null
    return null
  else if head.getNext() is null
    return head
  else
    tmpNode <- head.getNext()
    reset head.next to null
    return append(reverse(tmpNode), head)
*/

I assume that append() means append whatever the 2nd argument to the first argument. Not sure if this algorithm works at the moment. No program to test.

Thank you, that works well, although I think I'm supposed to incorporate pointerToLast and nextToLast for this particular assignment.

[Taywin]

That's the thing I don't understand... You don't really why you would need those methods. Though, there are many ways to implement it. I think your instructor may be sticking to his or her way too much...

[jon.kiparsky]

It seems to me that the nextToLast and the pointerToLast methods are useful for an iterative solution, not so much for the recursive. Come to think of it, the nextToLast isn't much use in an iterative situation, either, and of course as a practical matter it's impossible to keep it up to date in a singly linked list without traversing the list each time you pop something, so it seems like an odd construct altogether.
Don't beat your prof up too much on this one, but you might want to ask a few searching questions. Such as, why would you have a "nextToLast" method for a singly linked list, why wouldn't you just make it doubly linked if you need that functionality?