Reverse a linked list algorithm
Basics
Linked list is a data structure each element of those has link to the next element.
Each element of the linked list called node
The node of linked list called head. To identify the whole linked list we need link to head only.
The linked lists are great in insertion and deleting first and last elements. They can used for implementing stacks, queues.
Time and complexity for LinkedList
| Operation | Complexity explanation | Complexity formula |
| Insertion | constant | O(1) |
| Deletion | constant | O(1) |
| Search | linear | O(n) |
| Space | linear | O(n) |
Algorithm theory
Task definition
We have a linked list.
We need reverse items in the existing linked list.
Solution
The simplest way to solve the task is to iterate through the list and set the previous node as the next node for each node. The next node for the first node must be null.
The complexity in this case will be 0(n).
Diagram
Sample code
Below you will get a link to GitHub repo with Kotlin, Java, and Python source code
0 Comments