How to reverse a singly linkedlist?
Task
Reverse a singly linked list:
public ListNode reverseList(ListNode head) {
// todo
}
Solution
I will provide a solution to this problem in java.
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
ListNode next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}
First we need to think how many references do we need.
We know that in order to reverse a linked list we will have to iterate all elements. There's no other way.
So what information we should keep track of?
Well, obviously we need to know what is our current element.
We need to know to what is previous and next element to the current.
So that makes 3 references.
prev is initalized with null - you can think of it as an element before the head.
next is initialized with null as well.
We start iteration with the head element.
In order to reverse a linked list we set the current element's next reference to prev.
Then we change prev to reference to current element.
And eventually we set the current element to next.
That's it! It's complexity is O(n) - linear time.
Please comment if you have any questions, and upvote this post if you liked it!