Write a program to Delete loop in a linked list

The problem, simply

You get a linked list that may have a loop: the last box points back to an earlier box instead of to null. Remove the loop so the chain ends in null again, without losing any box. If there is no loop, leave the chain alone.

To cut the loop you must find one special box: the last box of the loop, the one whose next points back to where the loop starts. Set its next to null.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a guest book of boxes, a hash set. Walk with prev and curr. The first time curr lands on a box already in the book, prev is the last box of the loop, so cut prev.next.

1. prev = null, curr = head.
2. If curr is in the book, set prev.next = null and stop.
3. Otherwise add curr to the book and step both forward.

import java.util.*;

class Solution {
    public ListNode removeLoop(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode prev = null;
        for (ListNode curr = head; curr != null; curr = curr.next) {
            if (seen.contains(curr)) {    // stepped back into the loop
                prev.next = null;         // prev is the last box of the loop
                break;
            }
            seen.add(curr);
            prev = curr;
        }
        return head;
    }
}

How long it takes: every box is visited once, O(n). Extra room: the book holds every box, O(n).

Way 2: the clever way

Three short walks with fingers, no book.

1. Find a meeting box. slow moves 1 box, fast moves 2. If fast reaches null, there is no loop; stop. If they meet, both are on the loop.
2. Find the loop start. Put slow back on the head and leave fast on the meeting box. Move both one box at a time. They meet exactly at the start of the loop.
3. Find the last box. Walk from the start around the loop until the box whose next is the start. Cut its arrow.

Why step 2 works: if the path before the loop has m boxes, then walking m boxes forward from the meeting box also lands on the loop start. So two fingers, one at the head and one at the meeting box, arrive at the start together.

class Solution {
    public ListNode removeLoop(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {     // step 1: find a meeting box
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) return head;   // no loop

        slow = head;                                     // step 2: find the loop start
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        ListNode last = slow;                            // step 3: find the last box
        while (last.next != slow) last = last.next;
        last.next = null;                                // cut the loop
        return head;
    }
}

How long it takes: step 1 is at most about one walk plus one lap, step 2 at most m steps, step 3 one lap. All together O(n). Extra room: three fingers, O(1). When the loop starts at the head, step 2 ends at once, and step 3 still walks the full lap to find the real last box, so that case needs no special code.

Watch out for

• No loop: fast reaches null. Check this before step 2, or step 2 runs off the end.
• Use == on boxes, never their numbers.
• In C or C++ you only cut an arrow here; nothing is freed, since every box is still part of the chain.

What interviewers ask next

• Prove step 2. Say m boxes come before the loop and the loop has k boxes. When they meet, slow walked m + a boxes and fast walked twice that, which is m + a plus some whole laps. So m + a is a multiple of k, and walking m more boxes from the meeting point completes a lap and lands on the start.
• How long is the loop? From the meeting box, count steps until you are back.
• Can you do it with the loop length? Yes. Count the loop length k, put one finger k boxes ahead of another at the head, then move both until they meet at the start. Watch the head case again.
• How do you know you did not lose boxes? Count boxes with the hash set version before and with a normal walk after. Both must match.

Remember this

Grown-up words: the loop is a cycle, the two trains are slow and fast pointers (Floyd's tortoise and hare), the switch is the cycle's entry node, and the guest book is a hash set of nodes.