In this article, we discussed a problem: How to reverse a linked list in O(n) time complexity means in single traverse. In this, we are using the Singly LinkedList.
In order to reverse the linked list, we traverse the linked list and change the pointers address between two nodes which are adjacent to each other. Suppose we have below list:
Example: 1⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5.
As per the above list, node 1 having the address of node 2, node 2 having the address of node 3, node 3 having the address node 4 and so on. But last node 5 having null on address part.
After reverse, it becomes 1 ⇐ 2 ⇐ 3 ⇐ 4 ⇐ 5.
Now the node 5 having the address of node 4 which is earlier null and the same way node 4 having the address of node 3 where we earlier have node 5 address, node 3 having the address of node 2 where we have node 4 address and node 1 null on address part.
Below is the code sample in Java using iterative approach:
Node reverse(Node node) {
Node prev = null;
Node curr = node;
Node next = null;
while(curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
node = prev;
return node;
}
After reversing the linked list, the head is pointing to node 5.
Reversing the linked list with below:
Time Complexity: O(n)
Space Complexity: O(1)