× logo Home HTML CSS Javascript React-App Angular logo
logo

Mastering Top 10 Javascript Algorithms

**Algorithm Name**: Linked List Reversal

* **Questions**:
- What is the structure of the linked list node?
- Should it modify the original list or return a new one?

* **Time Complexity**:
- Optimized: O(n)

* **Space Complexity**:
- Optimized: O(1)

* **Approaches**:
- Optimized: Here is a one-pass, O(n) time, O(1) space complexity iterative approach that scans the linked list, setting the `next` pointer of each node to the previous node.

* **Explanation**:
This algorithm walks over the linked list node by node.
In each step, it switches the 'next' of the node to be the previous node. By the end of the traversal, every 'next' pointer has been redirected backwards hence achieving the reversal of the linked list.

* **Sample Code**:javascript

function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}

function reverseList(head) {
let prev = null;
let current = head;
while(current !== null){
// Store next node before we overwrite current.next
let nextTemp = current.next;

// Reverse current node's pointer
current.next = prev;

// Move pointers for next loop
prev = current;

current = nextTemp;
} return prev;
}

// Unit Test
let node5 = new ListNode(5);
let node4 = new ListNode(4, node5);
let node3 = new ListNode(3, node4);
let node2 = new ListNode(2, node3);
let node1 = new ListNode(1, node2);
let reversedList = reverseList(node3);
while(reversedList !== null)
console.log(reversedList.val);

* **Example**:
- Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
- Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL



logo