Tasks
Fast and Slow Pointers
April 2023
Index
Name
Number
Difficulty
Link
2
Remove Nth Node From End of List
19
Medium
7
Intersection of Two Linked Lists
160
Easy
// 141. Linked List Cycle
// Time: O(n) | Space: O(1)
var hasCycle = function(head) {
if (!head?.next) {
return false;
}
let slow = head;
let fast = head.next;
while (fast && fast !== slow) {
slow = slow.next;
fast = fast.next?.next;
}
return fast === slow;
};
/*
Fast and Slow Pointers
----------------------------
1. Iterate over till fast && fast !== slow.
2. Return fast === slow.
----------------------------
Time: O(n) | Space: O(1)
*/// 19. Remove Nth Node From End of List
// Time: O(n) | Space: O(1)
var removeNthFromEnd = function(head, n) {
let fast = head;
let slow = head;
let prev = null;
for (let i = 0; i < n; i++) {
fast = fast.next;
}
while (fast) {
prev = slow;
slow = slow.next;
fast = fast.next;
}
if (!prev) {
head = slow.next;
} else {
prev.next = slow.next;
}
return head;
};
/*
Fast and Slow Pointers
----------------------------
1. Move fast pointer n nodes ahead.
2. Move slow and fast to next till the fast is the end of the list.
3. Use slow prev to point to slow next to skip slow (n-th node from the end).
4. Return head.
----------------------------
Time: O(n) | Space: O(1)
*/// 876. Middle of the Linked List
// Time: O(n) | Space: O(1)
var middleNode = function(head) {
let slow = head;
let fast = head;
while (fast?.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
/*
Fast and Slow Pointers
------------------------
1. Iterate over with fast and slow.
2. When fast is null -> return slow.
------------------------
Time: O(n) | Space: O(1)
*/// 142. Linked List Cycle II
// Time: O(n) | Space: O(1)
var detectCycle = function(head) {
const getCycleLength = (start) => {
let length = 0;
let pointer = start;
while (true) {
pointer = pointer.next;
length++;
if (pointer === start) {
return length;
}
}
}
const getCycleStart = (head, length) => {
let pointer_1 = head;
let pointer_2 = head;
for (let i = 0; i < length; i++) {
pointer_2 = pointer_2.next;
}
while (pointer_1 !== pointer_2) {
pointer_1 = pointer_1.next;
pointer_2 = pointer_2.next;
}
return pointer_1;
}
let slow = head;
let fast = head;
let length = 0;
// 1. Find cycle.
while (fast?.next) {
slow = slow.next;
fast = fast.next.next;
if (fast === slow) {
// 2. Find cycle length.
length = getCycleLength(slow);
// 3. Find cycle start.
return getCycleStart(head, length);
}
}
// 4. If cycle is not found.
return null;
};
/*
Fast and Slow Pointers
---------------------------
1. Find cycle.
2. Find cycle length.
3. Find cycle head.
3. Return null if cycle not found.
---------------------------
Time: O(n) | Space: O(1)
*/// 206. Reverse Linked List
// Time: O(n) | Space: O(1)
var reverseList = function(head) {
if (!head || !head.next) {
return head;
}
let prev = null;
while (head) {
let next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
};// 234. Palindrome Linked List
// Time: O(n) | Space: O(1)
var isPalindrome = function(head) {
// 1. Handle corner cases.
if (!head || !head.next) {
return true;
}
// 2. Go with fast and slow.
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
// 3. Reverse from slow to the end.
let revertedHead = reverse(slow);
let tmpHead = head;
// 4. Go from tmpHead and revertedHead and compare.
while (tmpHead && revertedHead) {
if (tmpHead.val !== revertedHead.val) {
return false;
}
tmpHead = tmpHead.next;
revertedHead = revertedHead.next;
}
return true;
};
var reverse = function(head) {
let prev = null;
while (head) {
let tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
/*
Fast && Slow Pointers
---------------------------
0. Handle corner cases.
1. Go with fast and slow.
2. Reverse from slow to the end.
3. Go from head and rvertedHead and compare.
4. Return equal or not.
---------------------------
Time: O(n) | Space: O(1)
*/// 160. Intersection of Two Linked Lists
// Time: O(n) | Space: O(1)
var getIntersectionNode = function(headA, headB) {
const getListLength = (head) => {
let tmp = head;
let length = 0;
while (tmp) {
tmp = tmp.next;
length++;
}
return length;
}
// 1. Get length of each list.
let lenA = getListLength(headA);
let lenB = getListLength(headB);
let nodeA = headA;
let nodeB = headB;
// 2. Move longest start to the diff.
while (lenA > lenB) {
nodeA = nodeA.next;
lenA--;
}
while (lenB > lenA) {
nodeB = nodeB.next;
lenB--;
}
// 3. Iterate over both till the node is the same.
while (nodeA) {
if (nodeA === nodeB) {
return nodeA;
}
nodeA = nodeA.next;
nodeB = nodeB.next;
}
// 4. Return null if no intersection.
return null;
};
/*
Fast and Slow Pointers
------------------------------
1. Get length of each list.
2. Iterate longer start to the point where both length will be equal.
3. Iterate over both till the node is the same.
4. Return node if intersection and null if there is no intersections.
------------------------------
Time: O(n) | Space: O(1)
*/// 61. Rotate List
// Time: O(n) | Space: O(1)
var rotateRight = function(head, k) {
let tmp = head;
let end = null;
let idx = 0;
let length = 0;
while (tmp) {
if (!tmp.next) {
end = tmp;
}
tmp = tmp.next;
length++;
}
tmp = head;
k = k % length;
while (tmp) {
if (idx === length - k - 1) {
end.next = head;
head = tmp.next;
tmp.next = null;
break;
}
tmp = tmp.next;
idx++;
}
return head;
};
/*
Two Pointers
------------------------
1. Get list length.
2. Get end element.
3. Get element that will become new end.
4. Change poiners:
* current = [length - (k % length) - 1] element (new end)
* end.next = head
* head = current.next (new start)
* current.next = null
------------------------
Time: O(n) | Space: O(1)
*/// 148. Sort List
// Time: O(n log n) | Space: O(log n)
var sortList = function(head) {
if (!head?.next) {
return head;
}
let fast = head;
let slow = head;
// 1. Divide list into two halves
while (fast?.next?.next) {
slow = slow.next;
fast = fast.next.next;
}
let head_1;
let head_2 = slow.next;
slow.next = null;
// 2. Sort each half recursively
head_1 = sortList(head);
head_2 = sortList(head_2);
// 3. Merge two sorted halves
let tmpNode = { next: null };
let current = tmpNode;
while (head_1 && head_2) {
if (head_1.val < head_2.val) {
current.next = head_1;
head_1 = head_1.next;
} else {
current.next = head_2;
head_2 = head_2.next;
}
current = current.next;
}
// 4. Append any remaining nodes from one of the lists
if (head_1) {
current.next = head_1;
} else {
current.next = head_2;
}
// 5. Return head of merged list
return tmpNode.next;
};
/*
Fast and Slow Pointers
--------------------------
* Handle corner cases.
1. Iterate over list with fast and slow.
2. Divide list into 2 parts by slow pointer.
3. Use recursive calls for both halfs to divide furher. Save results as head_1 and head_2.
4. Iterate over head_1 and head_2 to compare values and to merge halfs back.
--------------------------
Time: O(n log n) | Space: O(log n)
*/// 202. Happy Number
// Time: O(log n) | Space: O(1)
var isHappy = function(n) {
const getSquaredSum = (val) => {
let result = 0;
while (val) {
result += (val % 10) ** 2;
val = Math.floor(val / 10);
}
return result;
}
let slow = n;
let fast = getSquaredSum(n);
while (fast !== 1 && fast !== slow) {
slow = getSquaredSum(slow);
fast = getSquaredSum(getSquaredSum(fast));
}
return fast === 1;
};
/*
Fast and Slow Pointers
------------------------------
1. Iterating over squares will lead us to 1 or to cycle on different number.
2. We go with slow and fast pointers.
3. Once the break condition is met -> exit from cycle.
4. Return fast === 1.
------------------------------
Time: O(log n) | Space: O(1)
*/Last updated
Was this helpful?