Reverse, middle and cycle detection in Python

Why it matters

These three problems are among the most common linked-list questions in interviews, and they are short enough to write under pressure. Each one teaches a pointer technique you will reuse on other problems. Reversal teaches you to rewire links without losing the rest of the list. Finding the middle teaches the slow-and-fast pointer pair. Cycle detection uses the same pair in a different way, and it finds the exact node where a loop begins. The lesson also shows the same reversal written recursively, because interviewers often ask for both versions.

The setup

A linked list is a chain of small objects called nodes. Each node holds a value and a link to the next node. The last node links to None, which is Python's word for "nothing here". Every program in this lesson uses the same node class. Call it ListNode to match the common interview wording.

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

__init__ is the method Python runs when you create a node. self is the node being set up. The default next=None means a new node points at nothing, unless you pass it a next node.

Two helpers make the examples short. build takes any number of values and returns the first node of a new list. show prints a list in the arrow form used in this course. build uses a dummy node, a placeholder placed in front of the list, which lesson 4 explains in full. The programs below include the helpers they need, so each one runs on its own.

The functions in this lesson are plain functions at the top level of the file. They are not methods on a class. Each one receives the list it works on as a parameter.

Two comparison operators matter in this lesson. is asks whether two names point at the same object. == asks whether two values are equal. Two separate nodes can hold the same number, so they are equal in value but not the same object.

a = ListNode(5)
b = ListNode(5)
print(a is b)
print(a.val == b.val)

False
True

If you know Java, None plays the role of null, and is plays the role of == on object references.

Reversing by rewiring

Reversing a list means changing each next link so it points backward. The node that was last becomes first, and the node that was first becomes last. No values move. Only the links change, so the work is O(n) time and O(1) extra space. O(n) means the time grows in step with the number of nodes. O(1) means the extra memory stays the same size however long the list is.

Think of a line of people holding hands, facing forward. To reverse the line, each person turns around in turn. The first person turns to face nobody, because they are now the last. The second person turns to face the first. The process continues down the line. The danger is in the step where a person turns around. If the person turns before they have let go of the next person's hand, the rest of the line is lost. The fix is to remember who was next before you turn.

Use three variables. prev holds the node that comes before the current one in the new order, which starts as None. cur holds the node you are working on, which starts at the head. nxt holds the node after cur in the old order, which you save before you change any link. Each step saves nxt, points cur.next at prev, and then moves prev and cur forward by one.

The variable is called nxt and not next, because next is a built-in function in Python. Using the name next for a variable works, but it hides the built-in and confuses readers.

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next          # save the rest of the list
        cur.next = prev         # turn this node around
        prev = cur              # prev moves onto this node
        cur = nxt               # cur moves onto the saved node
    return prev                 # prev is the new head

The function returns prev, not cur. When the loop ends, cur is None, because it walked past the old last node. prev holds the old last node, which is now the first. Returning cur is one of the most common mistakes, and the mistakes section shows what it looks like.

Python can also write the loop body on one line. The right side of the assignment is computed completely before any name changes, so the old values are used:

cur.next, prev, cur = prev, cur, cur.next

The loop condition can be while cur: instead of while cur is not None, because a node object is always true. The longer form is clearer for beginners, and it stays correct if a class ever defines truth rules of its own.

Trace the function on 1 -> 2 -> 3 -> None. The table shows the values at the start of each pass through the loop.

After pass 3, prev is node 3, and the chain reads 3 -> 2 -> 1 -> null. The first pass cut the old head's link to the rest of the list, which is why saving nxt first matters. The nodes never move in memory. Only the links turn, and the final chain is the reversed list.

Reversing recursively

A recursive function solves the same problem by calling itself on a smaller list. The idea is this: to reverse a list with a head h and a rest r, first reverse the rest, then make the first node of r point back at h, and make h the last node. The recursion stops when the list has zero or one node, because such a list is already reversed.

Read the code, then trace it.

def reverse_rec(head):
    if head is None or head.next is None:
        return head                      # zero or one node
    new_head = reverse_rec(head.next)    # reverse the rest
    head.next.next = head                # the node after head points back at head
    head.next = None                     # head becomes the last node
    return new_head                      # the same new head at every level

Trace 1 -> 2 -> 3. The call reverse_rec(1) sees that node 1 has a next, so it calls reverse_rec(2). That call sees node 2 has a next, so it calls reverse_rec(3). Node 3 has no next, so that call returns node 3 at once. Now the call for node 2 runs the remaining lines. Its head is node 2, and head.next is node 3. The line head.next.next = head sets node 3's next to node 2. The line head.next = None cuts node 2's old link to 3. The call returns node 3, which is the new head. The call for node 1 runs its lines: node 2's next is set to node 1, node 1's next is set to None, and the function returns node 3 again.

The recursion goes down to the last node and then back up, doing the rewiring on the way back. The new head comes from the bottom and is passed unchanged through every level. Each level does a constant amount of work after its recursive call returns, so the total time is O(n).

The recursive version uses O(n) extra space, because each call waits on the call stack until the deeper call returns. The iterative version uses three variables. For a list of a few hundred nodes this makes no difference. Python limits how many calls can wait at once. The default limit is 1000, and you can read it with sys.getrecursionlimit(). Reversing a list of 5000 nodes with reverse_rec raises a RecursionError. You can raise the limit with sys.setrecursionlimit, but that does not make the work cheaper, and a list of a million nodes would still need a million waiting calls. In an interview, mention this trade-off, and then say which version you would use for a very long list.

The next visualizer runs the recursive call stack step by step. Watch the calls go down to the last node and come back up. Each returning call performs its two rewiring lines.

The program below runs the recursive reversal on a list you give it as input. The first line is how many values follow, and the second line holds the values. Run it with this input:

5
1 2 3 4 5

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
 
def read_list():
    n = int(input())
    values = input().split()
    dummy = ListNode(0)
    tail = dummy
    for i in range(n):
        tail.next = ListNode(int(values[i]))
        tail = tail.next
    return dummy.next
 
 
def show(head):
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(parts + ["null"]))
 
 
def reverse_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head
 
 
head = read_list()
show(reverse_rec(head))

Output for the input above:

5 -> 4 -> 3 -> 2 -> 1 -> null

Finding the middle with two pointers

Finding the middle of a list is hard with one pointer, because you do not know the length. You could count the nodes first and walk again, which takes two passes. The two-pointer trick finds the middle in one pass. Put two pointers at the head. The slow pointer moves one node per step, and the fast pointer moves two nodes per step. When the fast pointer reaches the end, the slow pointer is halfway.

The image to hold in your head is two runners on a track. The fast runner covers twice the distance of the slow runner in the same time. When the fast runner finishes the lap, the slow runner is at the halfway point. The list works the same way, because the fast pointer covers the list at twice the speed.

def middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next             # one step
        fast = fast.next.next        # two steps
    return slow

The loop condition does the key work. fast must not be None, because the next line reads fast.next. fast.next must not be None, because the line after that reads fast.next.next. Both tests must come first, and and stops at the first false test, so the second test never runs on a None node.

Trace the function on 5 nodes, 1 -> 2 -> 3 -> 4 -> 5. Each row shows the pointers after one pass.

The loop stops with fast on the last node, because fast.next is None. slow is on node 3, which is the middle of five nodes.

Now trace it on 4 nodes, 1 -> 2 -> 3 -> 4.

Here slow ends on node 3. With four nodes the middle is between 2 and 3. The function returns the second of the two middle nodes. If you need the first middle instead, change the condition to fast.next is not None and fast.next.next is not None. Interviewers often ask which one a question wants, so say your choice out loud.

Watch the two pointers in the visualizer. The gap between them grows by one node on each step, and the slow pointer ends at the halfway point when the fast pointer reaches the end.

Checking for a palindrome

A palindrome reads the same forward and backward, such as 1 2 3 2 1. To check a linked list, you need its two halves compared in opposite directions. The trick is to reverse the second half, then compare it with the first half from the front. You combine the middle finder and the reversal you just built.

The method has four steps. Find the first middle with the variant condition. Reverse the nodes after it. Walk the first half from the head and the reversed second half at the same time. If any pair differs, the list is not a palindrome. If the second half runs out first, it is. For a list of odd length, the middle node is left out of the comparison, and that is correct, because the middle of an odd palindrome can hold any value.

Run the program below with this input. The first line is the count, and the second line holds the values:

5
1 2 3 2 1

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
 
def read_list():
    n = int(input())
    values = input().split()
    dummy = ListNode(0)
    tail = dummy
    for i in range(n):
        tail.next = ListNode(int(values[i]))
        tail = tail.next
    return dummy.next
 
 
def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev
 
 
def is_palindrome(head):
    if head is None:
        return True
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow.next)
    a = head
    b = second
    while b is not None:
        if a.val != b.val:
            return False
        a = a.next
        b = b.next
    return True
 
 
head = read_list()
print(f"palindrome: {is_palindrome(head)}")

Output for the input above:

palindrome: True

Change the last value in the input to 4 and the output becomes palindrome: False. The loop compares node 1 with node 4 first, finds a difference, and returns False straight away. Python prints the Boolean values as True and False, with capital letters.

Note the choice of the first middle here. For 1 2 3 2 1, the variant condition makes slow stop on the middle node 3. The reversal starts at slow.next, which is node 2, so the second half is 2 1, reversed to 1 2. The comparison runs over the two halves: node 1 with 1, then node 2 with 2. Node 3 is never compared, and that is correct.

The palindrome function also shows why you should draw your work. On paper, write the two halves in a column, one above the other, and compare them line by line. Most palindrome bugs are off-by-one errors in the middle, and a drawing shows them at once.

Detecting a cycle

A cycle is a list where some node's next points back to an earlier node, so walking forward never reaches None. A cycle can appear by mistake, when a programmer links a node to the wrong place, and the walk runs forever. Detecting a cycle is a standard question, and the answer uses the same two pointers as the middle finder.

Floyd's method, named after the computer scientist Robert Floyd, moves the slow pointer one step and the fast pointer two steps. If the list has no cycle, the fast pointer reaches None and the walk stops. If the list has a cycle, both pointers enter the cycle, and the fast pointer keeps gaining on the slow one. Each round, the distance between them shrinks by one, because the fast pointer moves one step further than the slow pointer does. Eventually the distance is zero, and the two pointers are on the same node.

Picture a list of four nodes where the last node links back to node 2. The walk goes 1, 2, 3, 4, then 2 again, then 3, and so on. It never reaches None. The two pointers still meet, because the fast one gains a step on each round.

Here is the function.

def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:             # the pointers met: there is a loop
            return True
    return False                     # fast reached the end: no loop

The test is slow is fast, which checks whether both names point at the same node object. Comparing values with == would be wrong, because two different nodes can hold the same number. The mistakes section shows a list where that wrong test reports a cycle.

Why must the two pointers meet? Think about the moment both are inside the cycle. Let the cycle have length c. The fast pointer is some distance ahead of the slow pointer, counted along the cycle. Each round, the fast pointer moves two steps and the slow pointer moves one, so the distance changes by one. The distance cannot skip past zero, because it changes one at a time. Within c rounds at most, the fast pointer lands on the slow pointer. Before the pointers enter the cycle, the fast pointer just walks forward until it either reaches the cycle or the end.

Trace the function on 1 -> 2 -> 3 -> 4 -> 2, where node 4 points back to node 2. The cycle is 2, 3, 4.

On pass 2, fast moved from 3 to 4 and then to 2, because it followed the cycle. On pass 3, slow moved from 3 to 4, and fast moved from 2 to 3 to 4. They met on node 4.

Time is O(n) and space is O(1). A simpler method keeps a set of visited nodes. Python's set stores each node once and checks each new node against the ones already stored. That also works in O(n) time, but it costs O(n) space. The two-pointer method uses only two variables, and interviewers usually want you to mention this difference.

The next program puts the three operations together on fixed lists. It takes no input, so it can run as it is. It reverses a five-node list, finds the middle of a five-node list and a four-node list, and checks two lists for a cycle. The cycle test links the last node of a four-node list back to node 2.

Output:

5 -> 4 -> 3 -> 2 -> 1 -> null
3
3
True
False

The middle of four nodes is node 3, which is the second middle, as the trace above showed. The cycle test prints True because node 4 points back to node 2, so the walk never reaches None. The list with three nodes has no link back, so it prints False.

Finding where the cycle begins

Detecting a cycle is not enough for some questions. The interviewer may ask for the node where the cycle starts, which is the first node that is visited twice. Floyd's method answers this in two phases, and the second phase is the part people forget.

Phase one finds a meeting point. Run the slow and fast pointers until they meet, as in has_cycle. The meeting point is somewhere inside the cycle, but it is not necessarily the start. Phase two finds the start. Set one pointer back to the head, and leave the other on the meeting point. Move both one step at a time. They meet again at the first node of the cycle.

The reason is a little arithmetic, and you can follow it with a picture. Let a be the number of steps from the head to the start of the cycle. Let b be the number of steps from the start to the meeting point, along the cycle. Let c be the cycle length. When the pointers meet, the slow pointer has walked a + b steps, and the fast pointer has walked twice that, 2(a + b). The fast pointer has also gone around the cycle some whole number of times, say k times, so 2(a + b) = a + b + kc. That simplifies to a = kc - b. In plain words, the distance from the head to the cycle start is the same as the distance from the meeting point to the cycle start, going forward around the loop. So a pointer that starts at the head and a pointer that starts at the meeting point, moving one step at a time, arrive at the cycle start together.

def cycle_start(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            entry = head                 # phase two: restart one pointer
            while entry is not slow:
                entry = entry.next
                slow = slow.next
            return entry                 # the first node of the cycle
    return None                          # no cycle

The program below builds a list of six nodes and links the last node back to a chosen index. It runs the full function and prints the cycle start. Run it with this input. The first line is the number of nodes, the second line holds their values, and the third line is the index that the last node points back to:

6
1 2 3 4 5 6
3

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
 
def cycle_start(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            entry = head
            while entry is not slow:
                entry = entry.next
                slow = slow.next
            return entry
    return None
 
 
n = int(input())
values = input().split()
nodes = [ListNode(int(v)) for v in values[:n]]
for i in range(n - 1):
    nodes[i].next = nodes[i + 1]
back = int(input())
nodes[n - 1].next = nodes[back]          # the last node points back to index back
entry = cycle_start(nodes[0])
if entry is None:
    print("has cycle: False")
else:
    print("has cycle: True")
    print(f"loop starts at value {entry.val}")

Output for the input above:

has cycle: True
loop starts at value 4

Trace the two phases. Phase one: slow moves 1, 2, 3, 4 and fast moves 1, 3, 5, 4, so the two pointers meet on node 4 after three passes. Phase two: entry starts at node 1, and slow is on node 4. Pass 1: entry moves to 2, and slow moves to 5. Pass 2: entry is on 3 and slow is on 6. Pass 3: entry is on 4, and slow moves from 6 to 4, the node the last node points back to. They are the same object, so the loop starts at 4.

The program prints the value of the node, not its index. A list with repeated values would make that ambiguous, so in a real problem report the index instead.

What happens inside: names, objects and calls

Two ideas from lesson 1 explain why these functions behave as they do.

The first is that a variable is a name that points at an object. Assigning one name to another does not copy the object. It adds a second name for the same object. This is the source of many linked-list bugs in Python.

x = ListNode(1)
y = x
y.val = 99
print(x.val)
print(x is y)

99
True

Changing y.val changed the node that x also points at. In has_cycle, slow and fast are two names that can point at one node, and slow is fast checks whether they do. In the reversal, prev and cur point at the same node for a moment after you change its link. Keep that in mind when you read these functions, because a change through one name shows up through every other name that reaches the same node.

The second is the call stack. Each time reverse_rec calls itself, Python saves the current call's local variables, including head and new_head, and starts a new call. The waiting calls form a stack of frames. When the deepest call returns, its frame is removed, and the frame below it resumes right after its recursive call. The recursion works because each frame remembers its own head, so after the return it still knows which node to rewire. The recursion limit is the largest number of frames allowed at once.

Follow-up questions interviewers ask

Interviewers rarely stop after the first working version. They ask follow-up questions to see whether you understand the trade-offs, so prepare short answers to these.

Why not count the nodes first? You could count, then walk again to the middle, which is correct and takes two passes. The slow-and-fast method finds the middle in one pass, and it uses the same two variables for the cycle test. Say that the count version is fine for a small list, and that the one-pass version matters when the list is long or when it is read from a stream that can be walked only once.

Can cycle detection avoid extra memory? Yes. Floyd's method uses two variables, so the extra space is O(1). A set of visited nodes is easier to explain, but it costs O(n) memory. Interviewers usually want the O(1) answer, and they may ask you to describe the set version first and then improve it.

How do you know the cycle exists before you test? You do not know, and that is why the test is needed. A list built from outside data might be cyclic by mistake. The safe approach is to run the test before any walk that assumes the list ends at None. Otherwise the walk runs forever.

When is the recursive reverse dangerous? It uses O(n) call-stack space, one frame per node. A list of a few hundred nodes is fine. A list of several thousand nodes fails with RecursionError under the default limit. The iterative version uses O(1) space and has no such limit, so it is the safer choice for production code.

Why return prev from reverse? Because prev is the last node that was moved, and after the loop it is the new first node. Interviewers ask this to check that you understand the loop, not only that you memorised it. Explain it using the state of the list after the last pass.

Common mistakes and the messages you will see

Returning cur from reverse. When the loop ends, cur is None. Returning it gives an empty list, and show prints only null. If you print the return value directly, Python shows None. The fix is return prev.

Losing the rest of the list. If you set cur.next = prev before saving next, the rest of the list has no names pointing at it. Printing the reversed list then shows only the first node, followed by null.

h = build(1, 2, 3)
cur = h
prev = None
while cur is not None:
    cur.next = prev          # wrong: the old cur.next is gone now
    prev = cur
    cur = cur.next           # cur.next is now prev, not the old next node
show(prev)

1 -> null

The loop stops after one pass, because cur moved to None. Nodes 2 and 3 are still in memory, but no name points at them.

Save nxt first, every time.

Checking fast.next before fast. Writing while fast.next is not None and fast is not None is wrong, because fast.next is read before the None check on fast. When fast is None, Python stops the program. The message looks like this:

  File "/.../err_demo2.py", line 7, in middle_bad
    while fast.next is not None and fast is not None:
          ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'

The file path and line number depend on your machine and file name, so they will differ. Read the last line first. The error says that None has no attribute named next. The caret points at fast.next, which was read while fast was None. The fix is the order fast is not None and fast.next is not None.

Forgetting the second check in the middle finder. The loop while fast.next is not None: alone fails on a list of two nodes. After one step, fast becomes None, and the next test reads fast.next. The message is the same AttributeError as above. The safe form tests fast is not None as well.

Running show on a cyclic list. A printing loop on a list with a cycle never ends, so the program prints forever. If your program's output keeps growing, check for a cycle before you blame the printing code.

Using == on values for the cycle test. Writing slow.val == fast.val reports a cycle on a list with no loop, when two different nodes hold the same number. This small program shows the difference:

def has_cycle_by_value(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow.val == fast.val:
            return True
    return False
 
 
print(has_cycle_by_value(build(1, 2, 2)))
print(has_cycle(build(1, 2, 2)))

True
False

The first function compares values and reports a cycle that does not exist. The second compares node objects and is correct.

Calling middle on an empty list. middle(None) returns None, not a node. If the caller reads .val on the result, Python raises AttributeError: 'NoneType' object has no attribute 'val'. Check for an empty list before you call the function.

Debugging walkthrough

Suppose you wrote reverse returning cur, and printing the result shows null. The list has nodes, so something is wrong with the return. Follow the routine from lesson 1.

First, print the list before and after the call, so you know the input was fine. Second, trace the loop with a table like the one earlier in this lesson. Put cur and prev in the columns, and fill in one row per pass. The table shows that cur ends as None and prev ends as the old last node. That is the point where you see that the function returns the wrong variable.

Now suppose instead that has_cycle returns True on a list you believe has no cycle. Trace the two pointers on paper with the list drawn out. Check whether a next link points back to an earlier node, which is the only way a real cycle can form. If the list really has no cycle, the bug is in the pointers you are comparing. A common cause is comparing slow.next with fast, which is off by one step.

For both bugs, the best check is a tiny input, such as a list of two or three nodes, where you can trace every step by hand. Large inputs hide the pattern.

Variations and edge cases

Test each function on these lists.

• Empty list. reverse returns None. middle returns None, so check for it before you read .val. has_cycle returns False.
• One node. reverse returns the same node. middle returns that node. has_cycle returns False, and is_palindrome returns True.
• Two nodes. The middle is the second node. A two-node palindrome needs equal values.
• A cycle that starts at the head. Point the last node at node 1. Phase two returns node 1.
• A self-loop. Point the last node at itself. The cycle has length one, and the cycle start is that node.

A common variation is to reverse only the first k nodes. Use the same three variables, but stop the loop after k passes, then connect the old head to the node that comes after the reversed part. Another is to reverse the nodes between positions left and right, which needs a walk to position left - 1. Both are good practice, and both are in the exercises.

Interview patterns

Reversal in place. Use three variables and save nxt first. Say why you return prev.

The fast-and-slow pair. Use it for the middle, for the cycle test and for the cycle start. Say what the fast pointer gains on each step and why that matters.

Split, reverse and compare. A palindrome check is a middle, a reversal and a comparison. Naming the three steps shows that you can compose small tools.

Know the space cost. The iterative reversal uses O(1) extra space, while the recursive one uses O(n) call-stack space. The set-based cycle test uses O(n) space, and Floyd's test uses O(1). Mention both versions and say which you would choose.

Real-world uses

Cycle detection matters wherever a linked structure can be built by mistake. A pointer loop in a program can keep objects alive or make a walk hang, and tools that check data structures use this same two-pointer test. List reversal is used when a program needs to read a sequence from the end, such as walking a chain of messages from the newest message back to the oldest. The middle finder is used for splitting work in half, which is the first step of merge sort on a linked list, a topic lesson 4 touches on.

Practice

Try these before you open the answers. Trace each one on a short list.

Exercise 1 (easy). Write reverse_first_k(head, k) that reverses only the first k nodes and leaves the rest in order. Assume k is at least 1.

Show the answer

The loop is the usual reversal, stopped after k passes. The old head becomes the last node of the reversed part, so its next must point at the first node that was not reversed, which is cur. Without that line, the reversed part would end in None and the rest of the list would be lost.

def reverse_first_k(head, k):
    prev = None
    cur = head
    i = 0
    while i < k and cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
        i += 1
    if head is not None:
        head.next = cur
    return prev

Exercise 2 (easy). For a list with one node, what does middle return? Explain your answer in terms of the loop.

Show the answer

It returns that node. slow and fast both start on it. The loop condition tests fast is not None and fast.next is not None. fast.next is None, so the loop body never runs, and slow is still the single node.

Exercise 3 (easy). Write length_rec(head) that counts the nodes recursively.

Show the answer

Each call adds one for its own node and asks the rest of the list for its count. The base case is the empty list, which has length zero. The recursion depth equals the length, so this uses O(n) call-stack space.

def length_rec(head):
    if head is None:
        return 0
    return 1 + length_rec(head.next)

Exercise 4 (medium). Write reverse_between(head, left, right) that reverses the nodes from position left to position right, counting positions from 1. Assume 1 <= left <= right <= length.

Show the answer

The dummy node handles left = 1, where there is no node before the start. The loop reverses exactly right - left + 1 nodes. Afterwards prev is the new first node of the reversed part, and start is now its last node, so start.next must point at cur, the first node after it.

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(1, left):
        before = before.next                # stop on the node before position left
    start = before.next                     # the first node to reverse
    prev = None
    cur = start
    for _ in range(left, right + 1):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    before.next = prev                      # the reversed part starts after before
    start.next = cur                        # the reversed part ends before the rest
    return dummy.next

Exercise 5 (medium). Write first_middle(head) that returns the first of the two middle nodes when the list has an even number of nodes. Test it on 4 nodes and on 5 nodes.

Show the answer

For 4 nodes, slow stops on node 2, the first of the two middle nodes. For 5 nodes, it stops on node 3. The condition fast.next is not None and fast.next.next is not None stops one step earlier than the original, which gives the first middle. The function assumes a non-empty list, because fast.next would fail on None.

def first_middle(head):
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

Exercise 6 (medium). Write cycle_length(head) that returns the length of the cycle, or 0 if there is no cycle.

Show the answer

Once the pointers meet, they are on a node inside the cycle. Walking from that node until you return to it counts the cycle's nodes. The count starts at 1 for the meeting node, and cur starts at the node after it.

def cycle_length(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            count = 1
            cur = slow.next
            while cur is not slow:
                cur = cur.next
                count += 1
            return count
    return 0

Exercise 7 (medium). Explain why fast moves two nodes per step, and what would go wrong if both pointers moved one node per step.

Show the answer

If both moved one node per step, they would be on the same node after every step, so slow is fast would be true at once, and every list, cycle or not, would report a cycle. The extra step for the fast pointer is what separates them, and inside a cycle it is what makes them meet. Without a cycle the faster pointer just reaches None first, which is also the signal that there is no loop.

Exercise 8 (medium). Write remove_cycle(head) that breaks the cycle, if one exists, by setting the node just before the cycle's start to None.

Show the answer

The cycle start is found with cycle_start from this lesson. The node that points back at the start is the last node of the cycle, so the loop walks until cur.next is the start. Setting that link to None turns the cycle into a normal list ending at cur. This is O(n) time and O(1) extra space.

def remove_cycle(head):
    start = cycle_start(head)
    if start is None:
        return
    cur = start
    while cur.next is not start:
        cur = cur.next
    cur.next = None

Exercise 9 (hard). Write reorder(head) that changes a list L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> .... Use the middle, a reversal and a merge of the two halves.

Show the answer

The first half is the front of the list. Reversing the second half lets the two halves be interleaved by taking one node from each in turn. The loop saves both next links before rewiring, which is the save-before-overwrite rule again. The function needs the reverse function from this lesson, and it runs in O(n) time with O(1) extra space.

def reorder(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow.next)              # the second half, reversed
    slow.next = None                         # cut the list in two
    a = head
    b = second
    while b is not None:
        nxt_a = a.next
        nxt_b = b.next
        a.next = b
        b.next = nxt_a
        a = nxt_a
        b = nxt_b
    return head

Exercise 10 (hard). Explain, step by step, why the second phase of cycle-start detection works when the first meeting point is not the cycle start. Use the names a, b and c from this lesson.

Show the answer

Let a be the steps from the head to the cycle start, b the steps from the start to the meeting point, and c the cycle length. At the meeting point the slow pointer has walked a + b steps. The fast pointer has walked 2(a + b), which also equals a + b + kc for some whole number k of extra laps. So a + b = kc, which gives a = kc - b. Walking c - b steps forward from the meeting point lands on the cycle start. Since a = kc - b, walking a steps from the meeting point also lands there, because the extra whole laps change nothing. So a pointer that moves a steps from the head and a pointer that moves a steps from the meeting point arrive at the cycle start together. Phase two moves both pointers one step at a time and stops when they are the same node, which is at the start.

What you now know

• Reversal rewires next links. Save nxt before you change a link, and return prev, not cur.
• The recursive version reverses the rest first, then makes the next node point back at the current one. It uses O(n) call-stack space, and Python's default limit of 1000 calls makes a very long list fail with RecursionError.
• Slow and fast pointers find the middle in one pass. The fast pointer moves two nodes per step, and the loop condition must test both fast and fast.next, in that order.
• A palindrome check combines the middle finder, a reversal and a comparison.
• Floyd's test detects a cycle because the fast pointer gains one node per step on the slow one, so they must meet inside the loop.
• A second phase, with one pointer restarted at the head, finds the exact node where the cycle begins.