Reversing a singly linked list [Java]

Question

I was wondering if someone could help explain how to reverse a singly linked list without creating new nodes or changing data in the existing nodes. I am trying to study for finals and we had this question on a previous test. They don't release answers to the coding portions of the test and I haven't been able to figure it out.

They told us the best way to reverse it was by using a "runner technique" which I believe I understand what that is. They described it as using two pointers or counters to run through a list and gather information but I'm not sure how to use that to reverse a singly liked list. I was able to brute-force code to reverse a list of length 2, 3, and 4 but I was unable to make a loop or do it recursively. Any code or an explanation on how to go about this would be appreciated, thank you.

Answer 1

You can derive the code by starting with the idea of merely - one by one - popping elements off the input list and pushing them onto an initially empty result list:

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    NODE head = <pop the first node off list>
    <push head onto result>
  }
  return result;
}

The result will be the reverse of the input. Now substitute Java for the missing pieces

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    // pop
    NODE head = list;
    list = list.next;
    // push
    head.next = result;
    result = head;
  }
  return result;
}

And you're done...