Reverse, middle and cycle detection

Why it matters

Reversing a list, finding its middle and detecting a cycle are the three questions that appear most often in linked list interviews. Each one looks like a small task, yet each shows whether you can move several pointers at once without losing a node. They are also the first problems where a simple loop is not enough. You need a second pointer, a saved pointer or a recursive call.

These three problems teach patterns that appear far beyond linked lists. Reversal teaches you to save a pointer before you change it. Finding the middle teaches the fast and slow pointer idea, which is also the basis of the two-pointer technique on arrays. Cycle detection teaches you to reason about what must happen when a pointer walks forever. By the end you will solve all three in O(n) time and O(1) extra space, and you will know how to explain why the answers are right.

The idea of reversal in plain words

Reversing a list means making the last node the first, the second last node the second, and so on, using the same nodes. You do not copy the values into a new list. You turn each next arrow around.

Imagine a row of people holding hands, facing right. To face them left, you turn each person around one at a time. Before you turn person 2, you must remember who person 3 is, because once person 2 turns, you can no longer reach person 3 from person 2. That remembering is the whole trick. Reversal is "save the next, turn the arrow, then step forward".

The loop needs three pointers. cur is the node being turned. prev is the node that has already been turned, so it points back at the nodes behind it. nxt holds the node ahead of cur, saved before the arrow changes. At the start, prev is nullptr, because the first node will become the last one and must end the list. At the end, prev is the new head.

Iterative reversal, step by step

Here is the iterative version. It loops once through the list, so it takes O(n) time, and it stores only three pointers, so it takes O(1) extra space.

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* nxt = cur->next;   // 1. save the rest of the list
        cur->next = prev;        // 2. turn the arrow of cur around
        prev = cur;              // 3. prev moves onto cur
        cur = nxt;               // 4. cur moves onto the saved node
    }
    return prev;                 // prev is the old last node, the new head
}

Trace it on the list 1, 2, 3, 4. Each row shows the list as three linked pieces: the part already turned (behind prev), and the part not yet turned (from cur on). The notation nullptr marks the end.

When cur becomes nullptr, the loop stops. prev points at node 4, which is now the first node of the list. The function returns it. The result reads 4, 3, 2, 1 when you follow the next links from node 4.

The trace shows why each line matters. Step 1 saves nxt before anything changes. If you wrote cur->next = prev; first, node 2 would be lost, because nothing else points to it. Step 2 turns the arrow, which is safe now because the rest of the list is saved. Steps 3 and 4 move both pointers forward. The order of these four lines is the most important thing to memorise about this function.

The picture below shows one step of the loop on three nodes. The arrow from node 2 to node 1 has just been flipped. Node 3 is saved in nxt and is still connected to node 2 only through the old arrow, which the next step will handle.

Three nodes during list reversal with prev, cur and nxt labelled, and the arrow between cur and prev flipped backwards

Here is the complete program. It reverses the list, prints it, and then reverses it back, so you can see that the same nodes are reused.

1 2 3 4
4 3 2 1
1 2 3 4

Notice that reverseList returns the new head. The caller must assign it, as in head = reverseList(head);. If you forget the assignment, head still points at node 1, which is now the last node with next equal to nullptr. Printing from it shows only 1. That is a classic bug, and it is easy to miss because the nodes are all still there.

Why reverse returns prev

Many students wonder why reverseList returns prev and not cur. The reason is in the loop's exit test. The loop runs while cur is not nullptr, so it stops only after cur has moved past the last node. At that moment cur is nullptr, which tells you nothing about the list.

The last node processed is the node that prev was set to in the final pass. That node had the old next of nullptr, so after its arrow was flipped it became the first node of the new list. In the trace on 1, 2, 3, 4 the final pass processed node 4, and prev is node 4 when the loop ends.

A quick rule covers it: the new head is the last node you turned, and prev always holds that node when the loop exits. Writing return cur; is a common mistake, and it returns nullptr for every list. Check the return line with a one-node list. A one-node list runs the loop once, prev becomes that node, and the function returns it correctly.

Recursive reversal

Iteration is the usual answer, but interviewers often ask for the recursive version too. Recursion means a function that calls itself on a smaller problem. For a list, the smaller problem is the list without its first node.

Think of reversing the list 1, 2, 3, 4 as two jobs. First, reverse the rest, 2, 3, 4, which gives 4, 3, 2. Second, attach node 1 to the end of that reversed rest, which is the node that was 2. The end of the reversed rest is always the old second node, because that node's next used to lead into the rest and now must lead back to 1.

Node* reverseRec(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;                       // empty or one node: already reversed
    }
    Node* newHead = reverseRec(head->next); // reverse the rest of the list
    head->next->next = head;                // the old second node now points back to head
    head->next = nullptr;                   // head becomes the new last node
    return newHead;
}

Trace it on 1, 2, 3. The call reverseRec(node1) sees that node 1 has a next, so it calls reverseRec(node2). That call calls reverseRec(node3). Node 3 has no next, so it returns node 3 at once.

Back in the call for node 2, newHead is node 3. The line head->next->next = head is node2->next->next, which is node3->next, which is set to node 2. So node 3 now points at node 2. Then node2->next = nullptr. The list is 3, 2, and node 2 is the last node. The call returns node 3.

Back in the call for node 1, newHead is still node 3. The line node1->next->next = node1 sets node2->next to node 1. Then node1->next = nullptr. The list is now 3, 2, 1, and the call returns node 3. The top-level caller gets node 3 as the new head.

The recursion goes as deep as the list is long, so it uses O(n) stack space. That is the trade-off: the code is short, but the call stack grows with the list. For a list of a million nodes, the recursive version may overflow the stack, while the iterative one uses only a few pointers. In an interview, give the iterative version first and mention the recursive one as a second answer.

The next picture shows the calls stacking up while the function waits for its smaller problem to finish, and then unwinding as each call fixes its own arrow.

Watch for the moment the calls start to return. Each call only changes its own node and the node after it, and the caller above it sees the list already reversed from that point on. The stack is what lets each call remember its own node while the deeper calls work.

Finding the middle with a slow and a fast pointer

The middle of a list is the node halfway along it. Counting the nodes first would take two passes. The fast and slow pointer method finds the middle in one pass.

Use two pointers. The slow pointer moves one node each step. The fast pointer moves two nodes each step. When the fast pointer reaches the end, the slow pointer has moved half as far, so it is at the middle. The fast pointer moves twice as quickly, so it covers the whole list in half the steps.

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

The loop condition has two parts. fast != nullptr guards the first step. fast->next != nullptr guards the second step, which moves fast twice. If fast is on the last node, fast->next is nullptr, so the second step would read nullptr->next. The condition stops the loop before that happens.

For a list with an odd number of nodes, the slow pointer lands on the exact middle. For a list with an even number, it lands on the second of the two middle nodes. That is the usual convention. If you need the first middle instead, change the condition to fast->next != nullptr && fast->next->next != nullptr. Always say which middle you mean in an interview.

The picture below shows the two pointers after each tick on five nodes. The slow pointer ends on the middle node, and the fast pointer on the last node.

Five nodes with slow pointing at the middle node 3 and fast pointing at the last node 5

Trace it on 1, 2, 3, 4, 5. Both pointers start at node 1. The table shows their positions after each step.

The loop stops with slow on node 3, which is the exact middle of five nodes.

Now trace the even case, 1, 2, 3, 4. Both pointers start at node 1. After step 1, slow is node 2 and fast is node 3. Check 2: fast is node 3, and its next, node 4, exists, so the loop runs. Slow moves to node 3 and fast moves to fast->next->next, which is nullptr. The check now fails at fast != nullptr, so the loop stops with slow on node 3. For the list 1, 2, 3, 4, the middle is node 3, which is the second of the two middle nodes, 2 and 3.

The fast pointer always moves two steps, so it can take the step that lands on nullptr in the middle of a double step. Look carefully at the second step of the even trace. Fast jumps from node 3 to nullptr. That is allowed here, because the loop checks fast before using it again.

Here is the complete program that checks both cases, plus a one-node list and an empty list.

middle of 5 nodes: 3
middle of 4 nodes: 3
middle of 1 nodes: 9
middle of 0 nodes: none

The output says middle of 1 nodes rather than 1 node. That is a plain label, so it is fine here, but it is a good habit to check plural wording in real output.

Detecting a cycle

A cycle is a list whose last next points back into the list, not to nullptr. The list no longer has an end, so a plain loop that stops at nullptr runs forever. The picture below shows one. The fourth node points back to the second.

Four nodes in a row where the fourth node's next pointer loops back to the second node

Floyd's cycle detection uses the same two pointers as the middle. The slow pointer moves one step and the fast pointer moves two. If the list has no cycle, the fast pointer reaches nullptr and the loop ends. If it has a cycle, both pointers walk into the loop and cannot avoid each other. The fast pointer gains one step on the slow pointer on every tick. Inside a loop of length L, the gap between them shrinks by one each tick, so they must meet within L ticks.

Here is the code.

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

The check slow == fast compares addresses, not data values. Two different nodes can hold the same number, and that does not mean a cycle. Only the same node reached twice means a cycle. Lesson 1's quiz covered this point, and it matters in every list problem.

Trace it on a list with a cycle: nodes 1, 2, 3, 4, 5, where node 5 points back to node 3. Both pointers start at node 1. Tick 1: slow is node 2, fast is node 3. Not equal. Tick 2: slow is node 3, fast is node 5. Not equal. Tick 3: slow is node 4, fast moves from node 5 to node 4 (node 5's next is node 3, then node 3's next is node 4). Slow and fast are both node 4, so slow == fast is true and the function returns true.

Now trace a list without a cycle: 1, 2, 3. Tick 1: slow is node 2, fast is node 3. Tick 2: fast is node 3 and its next is nullptr, so the loop condition fails before the move. The function returns false.

The method uses O(n) time and O(1) extra space. A different method stores each node's address in a set and checks each new node against it. That also works, and it is easy to explain, but it uses O(n) extra space. Floyd's method is the one interviewers expect when they say "in O(1) space".

Here is a complete program. It builds a five node list, checks it, adds a cycle, checks again, and prints yes or no. The program never prints the cyclic list, because printing a cycle loops forever.

before: no
after: yes

Notice that the program stores the nodes in a vector so it can link them by index. That is a convenience for the test. Real list code gets nodes from new and links them with next.

Why the two pointers must meet inside a cycle

Floyd's method works because of one fact about distances. Once both pointers are inside the loop, measure the distance from the slow pointer forward to the fast pointer, going around the loop. Each tick, the slow pointer moves one step and the fast pointer moves two. So the distance grows by exactly one per tick. A distance that grows by one each tick, around a loop of length L, must reach zero, which means the two pointers are on the same node, within L ticks.

Here is a concrete example. The list is a, b, c, d, e, and e points back to c. The loop is c, d, e, so L is 3. The tail, a and b, is outside the loop.

At tick 0 both pointers are on a. At tick 1 slow is on b and fast is on c. At tick 2 slow has entered the loop on c, and fast has moved from c to d to e, so fast is on e. Now both pointers are inside the loop. The forward distance from slow to fast is 2, because c to d to e is two steps.

At tick 3, slow moves from c to d, a distance of one. Fast moves from e to c to d, a distance of two, so fast is on d. Both pointers are on d, so they meet. The distance went from 2 to 3, and 3 is the same as 0 around a loop of length 3, which is exactly when the two pointers coincide.

The argument also shows that the meeting always happens. The distance cannot skip over zero, because it grows by one each tick. It is never stuck. A list with no cycle never gives a distance at all, because the fast pointer reaches the end first. That is why the test in hasCycle is correct for both kinds of list.

Finding where the cycle starts

A harder question is where the cycle begins. The answer uses the meeting point from Floyd's method, and it shows why the method is correct.

Let the distance from the head to the cycle start be a. Let the distance from the cycle start to the meeting point be b. Let the cycle have length L. When the two pointers meet, the slow pointer has moved a + b steps, and the fast pointer has moved twice that, 2(a + b). The fast pointer has also covered some whole number of loops, say k loops, so 2(a + b) = a + b + kL. Solving gives a = kL - b. In plain words: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start, measured around the cycle, plus some whole loops.

So if you put one pointer back at the head, and move both pointers one step at a time, they will meet at the cycle start. The first meeting is the start of the cycle.

Node* cycleStart(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            Node* p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;
        }
    }
    return nullptr;
}

Trace it on the list 1, 2, 3, 4, 5 where node 5 points to node 3. From the cycle detection trace, the meeting point is node 4. Reset p to node 1. Now p is node 1 and slow is node 4. Step: p moves to node 2, slow moves to node 5. Step: p moves to node 3, slow moves to node 3. Now they are equal, so the loop stops and the function returns node 3. The cycle starts at 3, which is correct.

Here is the program that prints the start value. It uses the same five node cycle as the detection program.

cycle starts at 3
no cycle

The second check breaks the cycle by setting node 5's next back to nullptr, then runs cycleStart again. The list is 1, 2, 3, 4, 5 with no cycle, so the function returns nullptr and the program prints no cycle.

Two-pointer thinking on arrays

The fast and slow pointer idea is one case of the two-pointer technique. You keep two positions in a sequence and move them by rules that depend on what they see. In an array, the two positions are often indices, such as one at the start and one at the end. The visualizer below shows two pointers moving toward each other on a sorted array, which is the array version of the same skill.

Watch how each move throws away part of the search. The pointers never need to revisit a position they have passed, which is why the method runs in O(n) time. The linked list version has the same property, but the second pointer moves by a different rule.

Common mistakes and the messages you will see

The most common reversal mistake is to lose the rest of the list. Writing cur->next = prev; before saving nxt makes the rest of the list unreachable. The program then prints only the first few nodes, and no error message appears. Save before you flip, every time.

A second reversal mistake is to forget to return the new head, or to ignore the return value. The caller still holds the old head, which is now the last node. Its next is nullptr, so printing from it shows only one value. The fix is head = reverseList(head);.

The most common middle mistake is to dereference after the end. Writing fast = fast->next->next; with only fast != nullptr as the loop condition crashes when fast is the last node. Under the address sanitizer the report reads SEGV on unknown address with a small address. The fix is the second check, fast->next != nullptr.

The most common cycle mistake is to print or walk a cyclic list with a plain loop. The program does not crash at first. It prints the same values forever, or it runs until you stop it. If a program prints the same numbers in a repeating pattern, suspect a cycle. A fast way to find it is to test with hasCycle before printing.

Another cycle mistake is to compare data instead of addresses. if (slow->data == fast->data) return true; reports a cycle for any list with two equal values next to each other in the right place. Compare pointers, as the code does.

A last mistake is a null check that is too late. In cycleStart, if you read p->next before checking p != slow, a list with no cycle is never reached, because the function returns nullptr first. The order of the checks in the loop matters, so read each while condition twice.

A debugging walkthrough

Suppose your reversal prints 4 3 2 1 for the first call and 1 for the second call. The first call is right. The second call prints one value, so the list has lost its links. Here is how to find the cause in five steps.

First, write the list state before and after each call on paper. Before the second call the list should be 4, 3, 2, 1, with head at node 4. If the program prints 1 for the second call, the head the second call received must be node 1, not node 4.

Second, check the caller. Look for reverseList(head); without head = in front of it. This is the most common cause. The function does reverse the nodes, but the caller still holds node 1, which is now the end of the list.

Third, if the caller is correct, trace the function on the list 4, 3, 2, 1 by hand. prev starts as nullptr, cur starts at node 4. The loop turns the arrows one by one. The final prev is node 1, the new head. The trace shows the function is correct, so the bug is outside it.

Fourth, check whether any code changed a next pointer between the calls. A print function that accidentally writes cur = cur->next in a loop that also changes the node is one example.

Fifth, print the head's address before and after each call. If the address changed and your code did not assign it, you have found the bug. If it did not change, the fault is elsewhere, and a print after each line inside reverseList shows the first line where the list stops making sense.

A palindrome check, traced

A palindrome reads the same forwards and backwards, such as 1, 2, 1 or 1, 2, 2, 1. To check a list, you can compare the first half with the reverse of the second half. The three tools from this lesson do the work: the middle finds where the halves split, reversal turns the second half around, and a loop compares the two halves node by node.

Take the odd list 1, 2, 1. The middle loop starts both pointers on node 1. The test fast->next != nullptr && fast->next->next != nullptr is true, since node 1 has a next and that next has a next too. So slow moves to node 2 and fast moves to node 1 at the end. Now fast->next is nullptr, so the loop stops. Slow is on node 2, the exact middle.

The second half starts after the middle, so it is node 1 at the end. Reversing a single node returns it unchanged. The code then cuts the first half off from the middle, so the first half is 1, 2 and the second half is 1. The comparison loop checks 1 against 1, which matches. Then node 2 is compared with nullptr, so the loop stops. The answer is true.

Now take the even list 1, 2, 2, 1. The loop stops with slow on the first 2, the first middle node. The second half is 2, 1, which reversed is 1, 2. The first half is 1, 2. Comparing 1 with 1 and 2 with 2 gives true.

A list that is not a palindrome, such as 1, 2, 3, fails at the first mismatch. Its middle is node 2. The second half is 3, which is compared with the first value, 1. They differ, so the function returns false.

The cost is O(n) time, because each step does a bounded amount of work, and O(1) extra space, because the reversal happens in place. The price is that the list changes while the check runs. A tidy version reverses the second half back before it returns. Interviewers often ask for that restore step, so mention it before you write code.

Interview patterns for this lesson

Reversal is a pattern you can reuse. Reverse a whole list to read it backwards. Reverse a part of a list between two positions by saving the boundary nodes, reversing the middle, and reconnecting. Palindrome checking uses the middle, then a reversal of the second half, then a comparison. Each step of that check uses a pattern from this lesson.

For the middle, interviewers often ask "find the middle in one pass". Say the slow and fast pointer idea first, then explain the loop condition. Name the even case convention out loud. Many candidates forget that the answer changes for even lengths.

For cycles, the questions are "detect a cycle", "find the start of the cycle" and "find the length of the cycle". The detection is Floyd's method. The start is the second phase, which you can derive from the meeting point. The length is found by moving one pointer around the loop until it returns to the meeting point and counting the steps. Practice explaining the start-of-cycle proof in a few lines, because interviewers ask for the reason, not only the code.

A question that appears in many forms is "Is this list a palindrome?" The standard answer finds the middle with the slow and fast pointers, reverses the second half, and compares the two halves node by node. It uses O(n) time and O(1) extra space, and it restores the list if the interviewer asks you to. Mention that restoring the list needs a second reversal.

Practice

Try each exercise before opening the solution. Draw the pointers on paper for the first two, because the pictures make the order of changes clear.

1. Write Node* reverseSegment(Node* head, int from, int to) that reverses the nodes at indices from through to, inclusive, and returns the head. Assume 0 <= from <= to and that to is inside the list.

Node* reverseSegment(Node* head, int from, int to) {
    Node dummy(0);
    dummy.next = head;
    Node* before = &dummy;
    for (int i = 0; i < from; i++) before = before->next;
 
    Node* first = before->next;
    Node* prev = nullptr;
    Node* cur = first;
    for (int i = from; i <= to; i++) {
        Node* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    before->next = prev;
    first->next = cur;
    return dummy.next;
}

2. Write int lengthOfList(Node* head) using the slow and fast pointers. Explain in one sentence why it does not need to count nodes one by one.

3. Write bool isPalindrome(Node* head) for a list of integers. Use the middle, reverse the second half, and compare. You may change the list.

bool isPalindrome(Node* head) {
    if (head == nullptr || head->next == nullptr) return true;
    Node* slow = head;
    Node* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* second = reverseList(slow->next);
    slow->next = nullptr;
    Node* a = head;
    Node* b = second;
    bool same = true;
    while (a != nullptr && b != nullptr) {
        if (a->data != b->data) same = false;
        a = a->next;
        b = b->next;
    }
    return same;
}

4. Write int cycleLength(Node* head) that returns the number of distinct nodes in the cycle, or 0 if there is no cycle.

int cycleLength(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            int len = 1;
            for (Node* p = slow->next; p != slow; p = p->next) len++;
            return len;
        }
    }
    return 0;
}

5. Explain why the slow pointer moves one node and the fast pointer moves two nodes, and not three. Use the list 1, 2, 3, 4, 5 in your answer.

6. Given the list 1 -> 2 -> 3 -> 4 -> 5 with node 5 pointing to node 2, state what middle returns and what hasCycle returns. Show the positions of the pointers after each step of the cycle detection.

7. Explain what changes if the list in middle is an even length and you want the first middle node. Write the new loop condition.

8. Write Node* kthFromEnd(Node* head, int k) that returns the node k places from the end, with k equal to 1 meaning the last node. Use two pointers, with the gap of k nodes between them. Return nullptr if the list is shorter than k.

Node* kthFromEnd(Node* head, int k) {
    Node* fast = head;
    for (int i = 0; i < k; i++) {
        if (fast == nullptr) return nullptr;
        fast = fast->next;
    }
    Node* slow = head;
    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

9. Write Node* reverseRecursiveWithoutNull(Node* head) that handles the one-node list correctly. Explain why the base case is head->next == nullptr and not only head == nullptr.

10. A list has a cycle that starts at node 3 of 10 nodes and includes all nodes from 3 to 10. Which node does cycleStart return, and how many steps does the second phase take?

What you now know

• Reversal saves next, flips the arrow, then moves prev and cur forward. It returns the new head, and the caller must assign it.
• The recursive version reverses the rest of the list and attaches the head to its end. It is short but uses O(n) stack space.
• The middle comes from a slow pointer that moves one node and a fast pointer that moves two. The loop condition must check both fast and fast->next.
• A cycle is a list whose last next points back into the list. Floyd's slow and fast pointers meet inside a cycle, and that is the detection test. Compare addresses, not data.
• The start of a cycle is found by resetting one pointer to the head and moving both one step at a time until they meet.
• Each of these runs in O(n) time and O(1) extra space, and each is a common interview question.

The next lesson merges two sorted lists and removes the nth node from the end, using a dummy head node.