DSA for Interviews, From Zero

Part 9 · Lesson 36 · read

Reverse and Fast/Slow Pointers

Reverse a list, find the middle, and check if the list has a loop (a cycle).

On this page

  1. Reversing a list
  2. Traced: reversing 1 → 2 → 3
  3. The recursive version
  4. Slow and fast pointers: the middle
  5. Detecting a cycle (Floyd's algorithm)
  6. Why the fast pointer must catch the slow one
  7. Putting it together: palindrome list
  8. Reversing only part of a list
  9. Practice questions (7)
  10. Make it stick
  11. What's next

Reversing a list

Reversing a linked list means making the last node the first one and the first node the last one, by changing the links. It is the most common linked-list question. The idea is easy: turn every arrow around. The hard part is doing it without losing the rest of the list. You walk down the list one node at a time. For each node, you make its next point backwards instead of forwards. Three variables do the job:

  • cur — the node we are turning around right now.
  • prev — the node before it. It becomes cur's new next. It is also the head of the reversed part we have built so far.
  • next — a saved copy of cur.next. We need it because the link is about to be overwritten.
JavaScript
function reverseList(head) {  let prev = null;  let cur = head;  while (cur !== null) {    const next = cur.next;   // 1. save the rest of the list before we cut the link    cur.next = prev;         // 2. point this node backwards    prev = cur;              // 3. prev steps forward    cur = next;              // 4. cur steps forward  }  return prev;               // prev is the new head}console.log(toArray(reverseList(fromArray([1, 2, 3, 4])))); // [4, 3, 2, 1]console.log(toArray(reverseList(fromArray([7]))));          // [7]console.log(toArray(reverseList(null)));                    // []
Save next before you cut
The first line in the loop is const next = cur.next for a reason. If you write cur.next = prev first, you lose your only way to reach the rest of the list. Then the loop cannot continue. It is like cutting a rope before you have a grip on the other end.

Traced: reversing 1 → 2 → 3

step 1 / 17
Set up
prev = null, cur = head

prev will become the head of the reversed part. cur is the node we are about to turn around.

▶let prev = null, cur = head;2while (cur !== null) {3  const next = cur.next;4  cur.next = prev;5  prev = cur;6  cur = next;7}8return prev;
Variables
reversed[]
rest[1, 2, 3]
prev"null"
cur1
Console
(nothing printed yet)
'reversed' is the chain that starts at prev. 'rest' is the part cur has not reached yet. Each round moves one node from rest to the front of reversed. · interactive

It takes O(n) time (the work grows in step with the list length) and O(1) extra space (only a few variables, however long the list is). It reuses the same nodes and only changes arrows.

The recursive version

Recursion (a function that calls itself) reverses the list from the back. Trust the function to reverse everything after the head. Then only one job is left: make the second node point back at the head.

JavaScript
function reverseList(head) {  if (head === null || head.next === null) return head;   // 0 or 1 node: already reversed  const newHead = reverseList(head.next);                 // reverse everything after head  head.next.next = head;                                  // the node after head must now point back at head  head.next = null;                                       // head becomes the tail  return newHead;}console.log(toArray(reverseList(fromArray([1, 2, 3, 4])))); // [4, 3, 2, 1]

Take 1 → 2 → 3. The call on 3 returns 3 (the base case, the simplest case that stops the recursion). Back in the call on 2, head.next.next = head makes 3 point at 2, and head.next = null cuts the link 2 → 3. Back in the call on 1, the same step makes 2 point at 1. This takes O(n) time. It also uses O(n) stack space. The call stack is the computer's list of unfinished function calls, and it holds one entry (frame) per node. A very long list can overflow it. The loop version has no such risk, so write the loop version first.

Slow and fast pointers: the middle

To find the middle of a list, you could count the nodes and then walk half of that. That needs two passes. The slow and fast pointer trick (two pointers that walk the same list at different speeds) needs only one. Start both pointers at the head. Each round, slow moves one node and fast moves two. It is like two runners where one is twice as fast. When fast reaches the end, slow has covered half the distance. So it is at the middle.

JavaScript
function middleNode(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;          // 1 step    fast = fast.next.next;     // 2 steps  }  return slow;                 // when fast reaches the end, slow is halfway}console.log(middleNode(fromArray([1, 2, 3, 4, 5])).val); // 3console.log(middleNode(fromArray([1, 2, 3, 4])).val);    // 3  (the second of the two middles)
Dry run · list 1 → 2 → 3 → 4 → 5
RoundslowfastContinue?
start11fast and fast.next exist: yes
123yes
235fast.next is null: stop

When the list has an even number of nodes, the loop ends with fast = null and slow on the second middle node. If you need the first middle node, start fast one step ahead, or stop when fast.next.next is null.

Detecting a cycle (Floyd's algorithm)

A list has a cycle (a loop) if some node's next points back to an earlier node. Then walking never reaches null. One easy way to detect this is to remember every node you have seen in a Set (a collection that keeps each item once). But that costs O(n) memory. Floyd's tortoise and hare uses the same slow and fast pair and needs only O(1) memory. If there is a cycle, the fast pointer catches up with the slow one from behind (like a fast runner lapping a slow runner on a track), and they meet. If there is no cycle, fast simply reaches the end.

JavaScript
function hasCycle(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;    fast = fast.next.next;    if (slow === fast) return true;     // they can only meet if the list loops  }  return false;                         // fast fell off the end: no cycle}const list = fromArray([1, 2, 3, 4]);console.log(hasCycle(list));            // falselist.next.next.next.next = list.next;   // 4 now points back to 2: 1 -> 2 -> 3 -> 4 -> 2 ...console.log(hasCycle(list));            // true

Why the fast pointer must catch the slow one

Once both pointers are inside the loop, look at the gap between them, counted along the loop. Each round, fast moves two and slow moves one. So the gap changes by exactly one. A gap that shrinks by one each round must reach zero. It cannot jump over zero. That is why they meet, and why a step of 2 is safe. With steps of 1 and 3, the pointers could step past each other forever in some loops. After slow enters the loop, the meeting takes at most about one loop length of extra rounds. So the total is O(n).

Finding where the cycle starts
After the two pointers meet, put one pointer back at the head. Then move both one step at a time. They meet again exactly at the node where the cycle begins (LeetCode 142). The proof is a short piece of algebra about distances. In an interview, it is fine to know the result and the main idea of the proof.

Putting it together: palindrome list

Is 1 → 2 → 2 → 1 the same forwards and backwards? (A list like this is called a palindrome.) You cannot walk a singly linked list backwards. So combine the two tricks. First, find the middle with slow and fast. Second, reverse the second half in place (without making a copy). Third, compare the two halves, starting from the outside. This takes O(n) time and O(1) space. Copying the values into an array is simpler, but it uses O(n) space.

JavaScript
function isPalindrome(head) {  // 1. find the middle  let slow = head, fast = head;  while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }  // 2. reverse the second half  let prev = null, cur = slow;  while (cur !== null) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }  // 3. compare the first half with the reversed second half  let a = head, b = prev;  while (b !== null) {    if (a.val !== b.val) return false;    a = a.next; b = b.next;  }  return true;}console.log(isPalindrome(fromArray([1, 2, 2, 1])));    // trueconsole.log(isPalindrome(fromArray([1, 2, 3, 2, 1]))); // trueconsole.log(isPalindrome(fromArray([1, 2, 3])));       // false

This version leaves the second half of the list reversed. If the caller still needs the original list, reverse that half again before you return. Say this in an interview. Interviewers like to hear it.

Reversing only part of a list

To reverse positions left to right, you need a dummy head (an extra fake node at the front, because the section may start at node 1). You also need a careful order of pointer moves. The code below repeatedly takes the node after start and moves it to the front of the section. This way, start moves to the back by itself.

JavaScript
// Reverse the nodes from position left to right (1-based).function reverseBetween(head, left, right) {  const dummy = new ListNode(0, head);  let before = dummy;  for (let i = 1; i < left; i++) before = before.next;   // the node just before the section  const start = before.next;                              // will end up as the tail of the section  for (let i = 0; i < right - left; i++) {    const moving = start.next;        // take the node after start...    start.next = moving.next;         // ...unlink it...    moving.next = before.next;        // ...and put it at the front of the section    before.next = moving;  }  return dummy.next;}console.log(toArray(reverseBetween(fromArray([1, 2, 3, 4, 5]), 2, 4))); // [1, 4, 3, 2, 5]

Practice questions

Before you code, draw three or four nodes and move the arrows with a pencil. You can see most mistakes on paper.

Q1Reverse linked listEasy

Given the head of a singly linked list, reverse the list and return the new head.

Example 1
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: Every arrow is turned around.
Example 2
Input: head = [1, 2]
Output: [2, 1]
Explanation: Two nodes swap roles.
Example 3
Input: head = []
Output: []
Explanation: An empty list stays empty.
Stuck? Open one hint at a time
Hint 1
Before you change a node's next, save where the rest of the list is.
Hint 2
Keep a prev that starts as null. The first node must end up pointing at null.
Show all 3 solutions with explanations
Approach 1Iterate with prev / cur / next
The idea
  1. Start prev = null, cur = head.
  2. Save next = cur.next, point cur.next at prev.
  3. Move prev and cur forward. When cur is null, prev is the new head.
JavaScript
function reverseList(head) {  let prev = null, cur = head;  while (cur !== null) {    const next = cur.next;    cur.next = prev;    prev = cur;    cur = next;  }  return prev;}console.log(toArray(reverseList(fromArray([1, 2, 3, 4, 5])))); // [5, 4, 3, 2, 1]console.log(toArray(reverseList(fromArray([1, 2]))));          // [2, 1]console.log(toArray(reverseList(null)));                       // []
How it works

O(n) time, O(1) space. You visit each node once, and only the arrows change.

Approach 2Recursion
The idea

Reverse the rest of the list (everything after the head). Then make the old second node point back at the head. Last, cut the head's own link.

JavaScript
function reverseList(head) {  if (head === null || head.next === null) return head;  const newHead = reverseList(head.next);  head.next.next = head;  head.next = null;  return newHead;}console.log(toArray(reverseList(fromArray([1, 2, 3, 4, 5])))); // [5, 4, 3, 2, 1]
How it works

O(n) time, but also O(n) call-stack space (the memory that holds unfinished function calls). A list of 100,000 nodes can overflow the stack in JavaScript.

Approach 3Copy values into an array
The idea

Read the values into an array. Then write them back in reverse order. It is easy, but it changes the values instead of moving the nodes.

JavaScript
function reverseList(head) {  const vals = [];  for (let c = head; c !== null; c = c.next) vals.push(c.val);  for (let c = head; c !== null; c = c.next) c.val = vals.pop();  return head;}console.log(toArray(reverseList(fromArray([1, 2, 3])))); // [3, 2, 1]
How it works

O(n) time and O(n) space. This is fine as a first answer. But the interviewer will almost always ask next, "now do it in O(1) space".

Which approach should you use?

Use the loop version. Also know the recursive version and its stack cost. (LeetCode 206.)

Q2Middle of the linked listEasy

Return the middle node of a linked list. If there are two middle nodes, return the second one.

Example 1
Input: head = [1, 2, 3, 4, 5]
Output: node 3
Explanation: There are five nodes, so the third one is in the middle.
Example 2
Input: head = [1, 2, 3, 4, 5, 6]
Output: node 4
Explanation: Two middles (3 and 4): return the second.
Stuck? Open one hint at a time
Hint 1
Counting the nodes works, but it takes two passes. Can two pointers moving at different speeds do it in one pass?
Show all 2 solutions with explanations
Approach 1Count, then walk
The idea

Pass 1 counts the nodes (n). Pass 2 walks floor(n / 2) steps (floor rounds down to a whole number).

JavaScript
function middleNode(head) {  let n = 0;  for (let c = head; c !== null; c = c.next) n++;  let mid = head;  for (let i = 0; i < Math.floor(n / 2); i++) mid = mid.next;  return mid;}console.log(middleNode(fromArray([1, 2, 3, 4, 5])).val);    // 3console.log(middleNode(fromArray([1, 2, 3, 4, 5, 6])).val); // 4
How it works

O(n) time, O(1) space, two passes.

Approach 2Slow and fast pointers
The idea

Each round, move slow one step and fast two steps. When fast reaches the end, slow is in the middle.

JavaScript
function middleNode(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;    fast = fast.next.next;  }  return slow;}console.log(middleNode(fromArray([1, 2, 3, 4, 5])).val);    // 3console.log(middleNode(fromArray([1, 2, 3, 4, 5, 6])).val); // 4
How it works

Same O(n) time and O(1) space, but in one pass. You will reuse this loop in almost every slow and fast pointer problem.

Which approach should you use?

Either one is accepted. The slow and fast version is what the question wants to see. (LeetCode 876.)

Q3Linked list cycleEasy

Return true if the linked list contains a cycle.

Example 1
Input: [3, 2, 0, -4], last node points back to the node with value 2
Output: true
Explanation: If you walk from the head, you never reach null.
Example 2
Input: [1, 2], no loop
Output: false
Explanation: The walk ends at null.
Stuck? Open one hint at a time
Hint 1
If you ever see the same node twice, there is a loop. How can you remember the nodes you have seen?
Hint 2
To use no extra memory, think of two runners on a round track.
Show all 2 solutions with explanations
Approach 1Remember visited nodes
The idea

Keep a Set (a collection with no repeats) of nodes. If the next node is already in it, there is a cycle. (Nodes are objects, so the Set checks whether it is the very same node, not just the same value.)

JavaScript
function hasCycle(head) {  const seen = new Set();  for (let c = head; c !== null; c = c.next) {    if (seen.has(c)) return true;    seen.add(c);  }  return false;}const a = fromArray([3, 2, 0, -4]);console.log(hasCycle(a));        // falsea.next.next.next.next = a.next;  // -4 points back at 2console.log(hasCycle(a));        // true
How it works

O(n) time, O(n) space.

Approach 2Floyd's tortoise and hare
The idea

Slow moves 1 step and fast moves 2 steps. Inside a cycle, fast gets one step closer to slow each round. So it must meet slow.

JavaScript
function hasCycle(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;    fast = fast.next.next;    if (slow === fast) return true;  }  return false;}const a = fromArray([3, 2, 0, -4]);a.next.next.next.next = a.next;console.log(hasCycle(a));                 // trueconsole.log(hasCycle(fromArray([1, 2]))); // false
How it works

O(n) time, O(1) space. Compare the nodes with ===, not their values. Two different nodes can hold the same value.

Which approach should you use?

Floyd's version is best. If you are not sure, start with the Set version and then improve it. (LeetCode 141.)

Q4Palindrome linked listEasy

Return true if the values of a linked list read the same forwards and backwards.

Example 1
Input: head = [1, 2, 2, 1]
Output: true
Explanation: It reads the same forwards and backwards.
Example 2
Input: head = [1, 2]
Output: false
Explanation: 1, 2 reversed is 2, 1.
Stuck? Open one hint at a time
Hint 1
You cannot read a singly linked list backwards. What can you do with one half of the list to fix that?
Show all 2 solutions with explanations
Approach 1Copy to an array
The idea

Put the values in an array. Then compare them with two pointers, one from each end, moving towards the middle.

JavaScript
function isPalindrome(head) {  const vals = [];  for (let c = head; c !== null; c = c.next) vals.push(c.val);  for (let i = 0, j = vals.length - 1; i < j; i++, j--) {    if (vals[i] !== vals[j]) return false;  }  return true;}console.log(isPalindrome(fromArray([1, 2, 2, 1]))); // trueconsole.log(isPalindrome(fromArray([1, 2])));       // false
How it works

O(n) time, O(n) space.

Approach 2Reverse the second half
The idea
  1. Find the middle with slow and fast pointers.
  2. Reverse the list from the middle onwards.
  3. Walk from the head and from the reversed half at the same time, and compare the values.
JavaScript
function isPalindrome(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }  let prev = null, cur = slow;  while (cur !== null) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }  for (let a = head, b = prev; b !== null; a = a.next, b = b.next) {    if (a.val !== b.val) return false;  }  return true;}console.log(isPalindrome(fromArray([1, 2, 3, 2, 1]))); // trueconsole.log(isPalindrome(fromArray([1, 2, 3])));       // false
How it works

O(n) time, O(1) space. When the length is odd, the middle node ends up in the reversed half. The comparison stops when the reversed half is used up, so the middle node is only compared with itself.

Which approach should you use?

The array copy is a good first answer. Then offer the O(1)-space version as the improvement, and say that it changes the list. (LeetCode 234.)

Q5Reverse linked list IIMedium

Reverse the nodes at positions left to right (1-based) and return the head.

Example 1
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]
Explanation: Only positions 2 to 4 are reversed.
Example 2
Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: A section of one node is unchanged.
Stuck? Open one hint at a time
Hint 1
The section can start at the head. So put a dummy node (an extra fake node) in front.
Hint 2
Walk to the node just before position left. From there, you change the links inside the section.
Show all 2 solutions with explanations
Approach 1Reverse the section, then reconnect
The idea
  1. Walk to before, the node in front of the section.
  2. Reverse right − left + 1 nodes with the normal loop.
  3. Reconnect the pieces: link before to the new section head, and link the old section head to the node that came after the section.
JavaScript
function reverseBetween(head, left, right) {  const dummy = new ListNode(0, head);  let before = dummy;  for (let i = 1; i < left; i++) before = before.next;  const sectionTail = before.next;           // will be last in the reversed section  let prev = null, cur = sectionTail;  for (let i = 0; i < right - left + 1; i++) {    const next = cur.next;    cur.next = prev;    prev = cur;    cur = next;  }  before.next = prev;                        // new head of the section  sectionTail.next = cur;                    // the rest of the list  return dummy.next;}console.log(toArray(reverseBetween(fromArray([1, 2, 3, 4, 5]), 2, 4))); // [1, 4, 3, 2, 5]console.log(toArray(reverseBetween(fromArray([5]), 1, 1)));             // [5]
How it works

O(n) time, O(1) space. It uses the reverse loop you already know.

Approach 2Move nodes to the front one at a time
The idea

Keep start where it is. Again and again, take the node after it and put it right after before.

JavaScript
function reverseBetween(head, left, right) {  const dummy = new ListNode(0, head);  let before = dummy;  for (let i = 1; i < left; i++) before = before.next;  const start = before.next;  for (let i = 0; i < right - left; i++) {    const moving = start.next;    start.next = moving.next;    moving.next = before.next;    before.next = moving;  }  return dummy.next;}console.log(toArray(reverseBetween(fromArray([1, 2, 3, 4, 5]), 2, 4))); // [1, 4, 3, 2, 5]
How it works

Same cost. It makes a single pass over the section and needs no final reconnect step. The downside is that it is easy to put the four assignments in the wrong order.

Which approach should you use?

The first one is easier to get right when you are under pressure. (LeetCode 92.)

Q6Swap nodes in pairsMedium

Swap every two nodes that sit next to each other, and return the head. Do not change the values inside the nodes. Change only the links.

Example 1
Input: head = [1, 2, 3, 4]
Output: [2, 1, 4, 3]
Explanation: Swap (1, 2) and (3, 4) by changing links, not values.
Example 2
Input: head = [1, 2, 3]
Output: [2, 1, 3]
Explanation: The last node has no partner, so it stays where it is.
Stuck? Open one hint at a time
Hint 1
You may change only the links. Use a dummy head and a prev pointer that sits just before each pair.
Show all 2 solutions with explanations
Approach 1Iterate with a dummy head
The idea
  1. prev sits just before a pair. Set a = prev.next and b = a.next.
  2. Change the links so the order becomes prev → b → a → (rest).
  3. Move prev to a, which is now the second node of the pair.
JavaScript
function swapPairs(head) {  const dummy = new ListNode(0, head);  let prev = dummy;  while (prev.next !== null && prev.next.next !== null) {    const a = prev.next, b = a.next;    a.next = b.next;    b.next = a;    prev.next = b;    prev = a;  }  return dummy.next;}console.log(toArray(swapPairs(fromArray([1, 2, 3, 4])))); // [2, 1, 4, 3]console.log(toArray(swapPairs(fromArray([1, 2, 3]))));    // [2, 1, 3]console.log(toArray(swapPairs(null)));                    // []
How it works

O(n) time, O(1) space.

Approach 2Recursion
The idea

Swap the first two nodes. Let the recursion handle the rest of the list, starting from the third node.

JavaScript
function swapPairs(head) {  if (head === null || head.next === null) return head;  const second = head.next;  head.next = swapPairs(second.next);  second.next = head;  return second;}console.log(toArray(swapPairs(fromArray([1, 2, 3, 4])))); // [2, 1, 4, 3]
How it works

The code is shorter, but it uses O(n) stack space.

Which approach should you use?

Use the loop. The question usually does not allow swapping values (a.val with b.val). (LeetCode 24.)

Q7Happy numberEasy

A happy number is a number that reaches 1 by the process below. Again and again, replace n with the sum of the squares of its digits. Return true if it reaches 1. Return false if it loops forever.

Example 1
Input: n = 19
Output: true
Explanation: 1²+9²=82, 8²+2²=68, 6²+8²=100, 1²+0²+0²=1.
Example 2
Input: n = 2
Output: false
Explanation: The numbers go round in a loop and never reach 1.
Stuck? Open one hint at a time
Hint 1
Replace the number with the sum of the squares of its digits, again and again. The result either reaches 1 or goes round in a loop. That is like a linked list that may have a cycle.
Show all 2 solutions with explanations
Approach 1Set of seen numbers
The idea

Keep making the next number. If it is 1, return true. If you have seen it before, you are in a loop, so return false.

JavaScript
function digitSquares(n) {  let sum = 0;  while (n > 0) { const d = n % 10; sum += d * d; n = Math.floor(n / 10); }  return sum;}function isHappy(n) {  const seen = new Set();  while (n !== 1 && !seen.has(n)) {    seen.add(n);    n = digitSquares(n);  }  return n === 1;}console.log(isHappy(19)); // trueconsole.log(isHappy(2));  // false
How it works

The numbers cannot keep growing. For a large n, the sum of the digit squares is much smaller than n. So the Set stays small.

Approach 2Floyd's slow and fast
The idea

Think of the sequence as a "list" where each number points to the next one. Run slow and fast along it. If they meet at 1, the number is happy. If they meet anywhere else, it is a loop.

JavaScript
function digitSquares(n) {  let sum = 0;  while (n > 0) { const d = n % 10; sum += d * d; n = Math.floor(n / 10); }  return sum;}function isHappy(n) {  let slow = n, fast = digitSquares(n);  while (fast !== 1 && slow !== fast) {    slow = digitSquares(slow);    fast = digitSquares(digitSquares(fast));  }  return fast === 1;}console.log(isHappy(19)); // trueconsole.log(isHappy(2));  // false
How it works

O(1) extra space. The lesson of this question: slow and fast pointers work on any sequence where "next = f(current)" (the next item comes from a rule applied to the current item), not just on linked lists. (LeetCode 202.)

Which approach should you use?

The Set is fine. Also mention Floyd's version as the option that needs only O(1) space.

Make it stick

Make it stick — close this page, then
  1. Write the loop version of reverse from memory. Say what prev, cur and next are each for.
  2. Explain why the slow and fast loop condition is fast !== null && fast.next !== null.
  3. Explain why the fast pointer cannot jump over the slow pointer inside a cycle.
  4. List the three steps of the palindrome-list solution.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Lesson 37 merges two sorted lists. Then it uses the slow and fast pointers and the gap trick again for harder questions: where a cycle begins, removing the n-th node from the end, where two lists meet, adding two numbers stored in lists, and sorting a list.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series