Skip to content

Instantly share code, notes, and snippets.

@xwlee
Created July 21, 2023 15:00
Show Gist options
  • Save xwlee/1e902db94515292fc35b7b7250016a5b to your computer and use it in GitHub Desktop.
Save xwlee/1e902db94515292fc35b7b7250016a5b to your computer and use it in GitHub Desktop.
linked-list.js
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor(value) {
const newNode = new Node(value)
this.head = newNode
this.tail = this.head
this.length = 1
}
printList() {
let temp = this.head;
while (temp !== null) {
console.log(temp.value)
temp = temp.next
}
}
getHead() {
if (this.head === null) {
console.log("Head: null")
} else {
console.log("Head: " + this.head.value)
}
}
getTail() {
if (this.tail === null) {
console.log("Tail: null")
} else {
console.log("Tail: " + this.tail.value)
}
}
getLength() {
console.log("Length: " + this.length)
}
// O(1)
push(value) {
const newNode = new Node(value)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++
return this
}
// O(n)
pop() {
// No item to pop
if (!this.head)
return undefined
let temp = this.head
let pre = this.head
while (temp.next) {
pre = temp
temp = temp.next
}
this.tail = pre
this.tail.next = null
this.length--
// Last item was popped
if (this.length === 0) {
this.head = null
this.tail = null
}
return temp
}
// O(1)
unshift(value) {
const newNode = new Node(value)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
newNode.next = this.head
this.head = newNode
}
this.length++
return this
}
// O(1)
shift() {
// No item to shift
if (!this.head)
return undefined
let temp = this.head
this.head = this.head.next
temp.next = null
this.length--
// Last item was shifted
if (this.length === 0) {
this.tail = null
}
return temp
}
// O(n)
get(index) {
if (index < 0 || index >= this.length) {
return undefined
}
let temp = this.head
for (let i = 0; i < index; i++) {
temp = temp.next
}
return temp
}
// O(n)
set(index, value) {
let temp = this.get(index)
if (temp) {
temp.value = value
return true
}
return false
}
// O(n)
insert(index, value) {
if (index < 0 || index > this.length)
return false
// Out of range
if (index === 0)
return this.unshift(value)
// Start
if (index === this.length)
return this.push(value)
// End
const newNode = new Node(value)
const temp = this.get(index - 1)
newNode.next = temp.next
temp.next = newNode
this.length++
return true
}
// O(n)
remove(index) {
if (index === 0)
return this.shift()
if (index === this.length - 1)
return this.pop()
if (index < 0 || index >= this.length)
return undefined
const before = this.get(index - 1)
const temp = before.next
before.next = temp.next
temp.next = null
this.length--
return temp
}
// O(n)
reverse() {
let temp = this.head
this.head = this.tail
this.tail = temp
let next = temp.next
let prev = null
for (let i = 0; i < this.length; i++) {
next = temp.next
temp.next = prev
prev = temp
temp = next
}
return this
}
findMiddleNode() {
// Initialize slow and fast pointers at head
let slow = this.head
let fast = this.head
// Iterate through the list
while (fast !== null && fast.next !== null) {
// Move slow pointer one step
slow = slow.next
// Move fast pointer two steps
fast = fast.next.next
}
// Return middle node when fast reaches end
return slow
}
// The "tortoise and hare" algorithm works by
// having two pointers move at different speeds
// through the linked list. If there is a loop,
// the faster pointer (the hare) will eventually
// catch up to the slower pointer (the tortoise)
// inside the loop. If there is no loop, the faster
// pointer will reach the end of the list.
hasLoop() {
// Initialize slow and fast pointers at head
let slow = this.head
let fast = this.head
// Iterate through the list
while (fast !== null && fast.next != null) {
// Move slow pointer one step
slow = slow.next
// Move fast pointer two steps
fast = fast.next.next
// If slow and fast pointers meet, loop exists
if (slow === fast) {
return true;
}
}
// If no loop is found, return false
return false
}
// The two-pointer technique used in this function
// ensures that the linked list is traversed only
// once, making the algorithm efficient with a time
// complexity of O(n), where n is the number of nodes
// in the list
findKthFromEnd(k) {
// Initialize slow and fast
let slow = this.head
let fast = this.head
// Move faster pointer k steps ahead
for (let i = 0; i < k; i++) {
// If fast reaches null, k is out of range
if (fast === null) {
return null
}
fast = fast.next
}
// Iterate until fast reaches the end
while (fast != null) {
// Move slow and fast pointers one step
slow = slow.next
fast = fast.next
}
// When fast reaches end, slow is at kth from end
return slow
}
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
myLinkedList.push(5);
myLinkedList.push(6);
// myLinkedList.tail.next = myLinkedList.head.next;
myLinkedList.findKthFromEnd(3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment