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.

you should check out this question: https://stackoverflow.com/questions/22605050/reverse-singly-linked-list-java?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa — MiguelD, May 06 '18 at 23:56

Gene · Answer 1 · 2018-05-07T00:12:16.677

2

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...

edited May 07 '18 at 00:12

answered May 06 '18 at 23:58

Gene

46,253
4
58
96

Thank you so much, that helps a lot. I just realized this creates a new node which I forgot we can't do. Is there any way to change this so I am not creating a new node? – Anthony Rulli May 07 '18 at 00:11
2

@AnthonyRulli no new `NODE`s have been created; references to existing nodes have merely been copied into variables. If you can't do that, there's no way to do even the simplest thing with a list. – Kevin Anderson May 07 '18 at 01:48
@AnthonyRulli Why do you think this creates new nodes? That would require calling `new NODE()`. As you can see, no such call is present. – Gene May 07 '18 at 17:18

score 0 · Answer 2 · answered May 07 '18 at 00:33

It depends on your implementation of the list, but I would recurse to the end and then reverse the references.

void Reverse(List pList) {
   Reverse(pList, null, pList.First); // initial call
}

void Reverse(List pList, Node pPrevious, Node pCurrent) {
   if (pCurrent != null)
      Reverse(pList, pCurrent, pCurrent.Next);   // advance to the end

   else { // once we get to the end, make the last element the first element
      pList.First = pPrevious;
      return;
   }

   pCurrent.Next = pPrevious; // reverse the references on all nodes
}

Reversing a singly linked list [Java]

2 Answers2