Here is code for implementing a singly-linked list:
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = {
value: value,
next: null,
};
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = {
value: value,
next: null,
};
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
reverse() {
if (!this.head.next) {
return this.head;
}
let first = this.head;
this.tail = this.head;
let second = first.next;
while (second) {
const temp = second.next; //third
second.next = first;
first = second;
second = temp;
}
this.head.next = null;
this.head = first;
return this.printList();
}
}
I need someone to help me understand this reverse()
function, I tried to understand it a lot of times, and I also tried with ChatGPT haha.
The reverse()
function runtime is O(n).
I’ll explain the code step-by-step.
First, we define the Node
class to represent each element in the linked list:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
Next, we create the LinkedList
class to manage the nodes:
class LinkedList {
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = new Node(value);
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
insert(index, value) {
if (index >= this.length) return this.append(value);
if (index === 0 || this.length === 0) return this.prepend(value);
const newNode = new Node(value);
const leader = this.traverseToIndex(index - 1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.next = holdingPointer;
}
traverseToIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
printList() {
let array = [];
let currentNode = this.head;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
return array;
}
Here is the reverse()
method which reverses the linked list in place:
reverse() {
if (!this.head.next) {
return this.head;
}
let first = this.head; // Start with the head node
this.tail = this.head; // The tail will become the original head
let second = first.next; // The second node
// Print the initial state
let list = this.printList();
console.log(`Initial list: ${list}
first = head = ${first.value}
tail = head = ${this.tail.value}
second = first.next = ${second.value}
`);
let n = 1;
console.log(`While second is not null:`);
// Reverse the pointers
while (second) {
console.log(`LOOP: ${n}
${list}
`);
const temp = second.next; // Store the next node
if (temp !== null) console.log(`temp = second.next = ${temp.value}`);
second.next = first; // Reverse the pointer of the current node
console.log(`second.next = first = ${second.next.value}`);
first = second; // Move first to the current node
console.log(`first = second = ${first.value}`);
second = temp; // Move second to the next node
if (second !== null) console.log(`second = temp = ${second.value}`);
n++;
console.log();
}
// Final adjustments
this.head.next = null; // The new tail should point to null
this.head = first; // The new head is the last node we processed
return this.printList();
}
}
To see the reverse()
method in action, you can create a linked list and call the method:
let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
console.log(myLinkedList.reverse()); // Output: [16, 5, 10]
Initialization:
first
starts at the head of the list.this.tail
is set to the original head.second
is the node next to first
.Loop Through the List:
second
in temp
.second
to point to first
.first
and second
one step forward.End of Loop:
first
) becomes the new head.this.tail
) points to null
.Result: