# Reversing a singly linked list

#### jonas

##### Ultra Cool Member
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:

#### Accname

##### 2D-Graphics enthusiast
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

#### jonas

##### Ultra Cool Member
it's quite much literally the same (minus a bug in my code)

#### Accname

##### 2D-Graphics enthusiast
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.

#### jonas

##### Ultra Cool Member
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?

#### Accname

##### 2D-Graphics enthusiast
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.

#### jonas

##### Ultra Cool Member
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".

#### Accname

##### 2D-Graphics enthusiast
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".

#### jonas

##### Ultra Cool Member
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.
• tom_mai78101:
Starting this upcoming Thursday, I will be in Japan for 10 days.
• tom_mai78101:
Thursday - Friday will be my Japan arrival flight. 9 days later, on a Sunday, will be my return departure flight.
+2
• The Helper:
Hope you have safe travels my friend!
+1
• vypur85:
Wow spring time in Japan is awesome. Enjoy!
• The Helper:
Hopefully it will be more pleasure than work
• vypur85:
Recently tried out ChatGPT about WE triggering. Wow it's capable of giving a somewhat legitimate response.
• The Helper:
I am sure it has read all the info on the forums here
• The Helper:
i think triggering is just scripting and chatgpt is real good at code
• vypur85:
Yeah I suppose so. It's interesting how it can explain in so much detail.
• vypur85:
But yet it won't work.
• The Helper:
it does a bad ass job doing excel vba code it has leveled me up at my job when I deal with excel that is for sure
• vypur85:
Nice! I love Excel coding as well. Has always been using Google to help me. Maybe I'll use ChatGPT next time when I need it.
• The Helper:
yeah whatever it puts out even if it is not perfect I can fix it and the latest version of chatgpt can create websites from pictures it will not be long until it can do that with almost all the tools
+1
• The Helper:
These new Chat AI programs are going to change everything everyone better Buckle the Fuck Up!
• The Helper:
oh and Happy Tuesday Evening!
+1
• jonas:
Im worried they'll change things for worse
• jonas:
A lot more low quality content, a lot more half-baked stuff.
• jonas:
If you're good enough to spot the mistakes of the answers you don't need it in the first place. If you aren't good enough, you're gonna rely on some half-correct stuff
• The Helper:
the earlier AI is and has been used extensively for publishing news and other content for a while now
• jonas:
I used to be active on quora, it's now flooded with extremely similar, superficial answers that often miss the point of the question
• N NJJ:
hi
• N NJJ:
Hello, gathering all my old accounts…
+1
• The Helper:
by all means gather it all up!