CODEWITHSUNDEEP
javasingly-linked-list
Anthony Rulli
Anthony Rulli

Reputation: 63

Reversing a singly linked list [Java]

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.

Upvotes: 4

Views: 862

Answers (2)

Dave Cousineau
Dave Cousineau

Reputation: 13148

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
}

Upvotes: 0

Gene
Gene

Reputation: 46960

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

Upvotes: 2

Related Questions