Reversing a singly linked list

jonas

News Fan!
Reaction score
73
Code:
rec_reverse(last_of_rev,to_rev) = if to_rev != nil:
  next_rev = to_rev.next;
  to_rev.next = last_of_rev;
  rec_reverse(to_rev,next_rev)

reverse(to_rev) = rec_reverse(nil, to_rev)

Code:
reversed list    list to be reversed
(|<-()<-...<-()  ,  []->()->...->()->|)
after one recurisve step becomes:
(|<-()<-...<-()<-[]  ,  ()->...->()->|)
at the end of recursion becomes:
(|<-()<-...<-()<-[]<-()<-...<-()  ,  |)
 
Last edited:
How about this?
Code:
    public void reverse() {
       Node prev = null;
       Node current = first;
       while (current != null) {
         Node next = current.next;
         current.next = prev;
         prev = current;
         current = next;
       }
       first = prev;
     }
This is using a simple while-loop.
Here a full example with test case:
Code:
  public static void main(final String[] args) {
     LList l = new LList();
     l.first = new Node("A");
     l.first.next = new Node("B");
     l.first.next.next = new Node("C");
     l.first.next.next.next = new Node("D");
     l.first.next.next.next.next = new Node("E");
     l.first.next.next.next.next.next = new Node("F");
    
     System.out.println(l);
     System.out.println();
     l.reverse();
     System.out.println(l);
     System.out.println();
   }
  
   public static class LList {
     Node first;
    
     public void reverse() {
       Node prev = null;
       Node current = first;
       while (current != null) {
         Node next = current.next;
         current.next = prev;
         prev = current;
         current = next;
       }
       first = prev;
     }
    
     @Override
     public String toString() {
       StringBuilder sb = new StringBuilder();
       Node current = first;
       while (current != null) {
         sb.append(current.value);
         sb.append(" ");
         current = current.next;
       }
       return sb.toString();
     }
   }
  
   static class Node {
     Object value;
     Node next;
    
     public Node(Object value) {
       this.value = value;
     }
    
   }
Output:
A B C D E F

F E D C B A
 
Its not quite the same depending on the execution enviroment and language you are using. A loop is much better in java than recursion. Sure, at some point the JIT will jump in and might improve the recursive method, but until then the loop will outperform the recursion every time.
 
Its not quite the same depending on the execution enviroment and language you are using. A loop is much better in java than recursion. Sure, at some point the JIT will jump in and might improve the recursive method, but until then the loop will outperform the recursion every time.

Note that I was not giving a java program... At the conceptual level the two are identical, and that was the level in which I was giving the algorithm. Yes, in a given actual implementation the performance between the two may differ significantly, and one of them may run out of memory while the other may not (this is actually the bigger issue). From my point of view, you have simply given the idiomatic Java implementation of the conceptual algorithm above. Maybe we can find common ground here?
 
You have to go to a veeeeerrrryyy high conceptual level to call these two implementations equal. Sure, in the end they do the same thing because thats what they are supposed to do. But both use different syntactic and semantic constructs some of which may or may not be available in a given language / runtime enviroment.
 
You have to go to a veeeeerrrryyy high conceptual level to call these two implementations equal. Sure, in the end they do the same thing because thats what they are supposed to do. But both use different syntactic and semantic constructs some of which may or may not be available in a given language / runtime enviroment.

The first one is not an implementation, it's a description of the algorithm. There might not even be a compiler or interpreter for that language.
I wouldn't just say that they do the same thing, I'd go as far to say they do it the *same way*, namely by going through the pointers and flipping them one by one. Recursion and iteration just say "repeatedly do this", or "repeatedly do this until".
 
Thats a little to vague for my taste. A loop is an actual syntactical structure defined by a language. Recursion is a method of software-developement that can be used in most languages but there is no syntactical component to it in any language I know of. There are many different languages, some of which do not have loops. Some of them do not have the concept of methods either but they have loops. Some have methods but do not allow for recursion, etc.
I can not say with a straight face that these two things are "the same". They might be very similar, they might be exchangeable in most enviroments, but they are not "the same".
 
Well, I understand that you live in the practical world of building real software, where there are very clearly specific definitions and precise differences for these definitions. If I would develop a Java program, I would use a while loop, not a recursive method call, just like you have.

I on the other hand live in the theoretical world of building language models and proving that can be compiled correctly to run on real machines, so I'm looking more at the conceptual level of what languages can do (in general) and how it would be compiled and run, and so in my world they use the same mechanisms and I don't distinguish between them. Whether a language implements "doing the same thing over and over" by function recursion or loop recursion or a recursion operator (like system T) is completely irrelevant to me; if it has a way of "doing the same thing over and over", it needs to do a) b) and c) to compile correctly for x86.
 
General chit-chat
Help Users
  • No one is chatting at the moment.
  • Varine Varine:
    Turns out it wasn't me and it wasn't E Coli, which I was sure it wasn't. But still very stressful. Do not recommend fucking with the CDC.
  • Varine Varine:
    I think the worst was the IRS. We got audited once and they show up with like guns and shit, because I guess the IRS is technically a police force?
  • Varine Varine:
    They had a gun and it was very unnerving.
  • Varine Varine:
    I looked up why and it does make sense though. I forget they are the ones that deal with like mafias and shit, and not everyone is going to be very considerate about being told they need to explain and prove where their money comes from. We'
  • Varine Varine:
    We are pretty good about it I think. Not my job, but the people that do it are pretty one top of it.
  • The Helper The Helper:
    yeah I dont like the government. I am a total libertarian and what you are describing is what I am totally against when it comes to governing
  • Varine Varine:
    I mean I don't really like the government. But I would also prefer to have one than... not have any government. Like we need to have police forces and national welfare systems, but I don't think the cop that is pulling you over for speeding is the same cop that should also be responding to active terror events.
  • The Helper The Helper:
    I am talking about federal.
  • The Helper The Helper:
    State and local elections I believe in when it comes to governing. Of course the military
  • The Helper The Helper:
    Federal should do military
  • The Helper The Helper:
    The federal government should do the military not the police. I hope Trump gets rid of the income tax
  • The Helper The Helper:
    I hold no hope of Trump getting rid of income tax though.
  • jonas jonas:
    Trump is a wildcard, but in the end, it's the republican party that makes the laws, Trump can only do exec orders
  • jonas jonas:
    I don't think the Republicans will get rid of income tax, at most lower it a little, mostly for people with 6 figures+. But that's just my opinion
  • The Helper The Helper:
    one can dream
  • Ghan Ghan:
    FairTax would be nice.
  • Ghan Ghan:
    But the electorate would have to demand it and vote people in to do it.
  • Ghan Ghan:
    Government spending, foreign policy, and the southern border are all bigger issues than the income tax right now I'd say.
  • The Helper The Helper:
    For you those are the bigger issues. Cannabis legalization and get rid of Income tax are mine.
  • Ghan Ghan:
    We have so much cannabis up here in Oklahoma. Can't go a block without running into 3 dispensaries. xD
  • The Helper The Helper:
    if the demand is there
  • jonas jonas:
    I think the biggest issue in USA is how divided the country has become
  • Ghan Ghan:
    There's a big split happening in fundamental values that is very worrisome.
  • jonas jonas:
    I think there's always been a split in values. But now there's a split in what reality is. No matter whom you ask, they think a third of the country is insane and wants to destroy the country
  • The Helper The Helper:
    pretty big split

      The Helper Discord

      Staff online

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top