Deletion from a Circular Linked List

The problem, simply

You get the head of a circular linked list: the last box points back to the head, not to null. You also get a key. Remove the box that holds key and give back the head of the ring.

The ring must stay a ring. If you remove the head, the next box becomes the new head and the last box must now point to it. If the ring has only one box and you remove it, the answer is an empty list, null. If no box holds key, give back the ring unchanged.

A story to remember it

Picture it

Examples

Way 1: the simple way

Treat the head as a special case.

1. If the list is empty, return null.
2. If the head holds key: if it is the only box, return null. Otherwise walk around to find the last box, point it at head.next, and return head.next.
3. Otherwise walk with prev and curr from the head. When curr holds key, set prev.next = curr.next. Stop when curr comes back to the head.

class Solution {
    Node deleteNode(Node head, int key) {
        if (head == null) return null;
        if (head.data == key) {
            if (head.next == head) return null;       // the only box
            Node last = head;
            while (last.next != head) last = last.next;   // walk around to the last box
            last.next = head.next;                    // close the ring without the head
            return head.next;
        }
        Node prev = head, curr = head.next;
        while (curr != head) {
            if (curr.data == key) {
                prev.next = curr.next;                // skip over the box
                return head;
            }
            prev = curr;
            curr = curr.next;
        }
        return head;                                  // key was not in the ring
    }
}

How long it takes: at most two trips around the ring, O(n). Extra room: two fingers, O(1).

Way 2: the clever way

Start checking at the second box and let the head be the last one you check. When you finally check the head, prev is already standing on the last box, which is exactly the box that must be rewired. One walk handles every case.

1. If the list is empty, return null. Put prev on the head and curr on head.next.
2. If curr holds key: if curr == prev, the ring had one box, so return null. Otherwise set prev.next = curr.next. If curr was the head, return curr.next as the new head, else return head.
3. If curr is the head and it did not match, you went all the way around. Return head.
4. Otherwise slide both one step and repeat.

If the key were 3, the walk would stop at the second check with prev on 2, set 2.next = 4, and return the old head.

class Solution {
    Node deleteNode(Node head, int key) {
        if (head == null) return null;
        Node prev = head, curr = head.next;   // the head is checked last
        while (true) {
            if (curr.data == key) {
                if (curr == prev) return null;    // it was the only box
                prev.next = curr.next;            // hold hands over the gap
                return curr == head ? curr.next : head;
            }
            if (curr == head) return head;        // all the way round, no key
            prev = curr;
            curr = curr.next;
        }
    }
}

How long it takes: at most one trip around the ring, O(n). Extra room: two fingers, O(1). Same big O as Way 1, but one walk instead of two when the head goes, and no special head branch.

Watch out for

• The one box ring. prev and curr are the same box, so return null. Writing prev.next = curr.next there would keep the box alive.
• A key that is not there. A while (curr != head) style loop is needed so you stop after one trip. A plain while (curr != null) never ends in a ring.
• Duplicate keys. Way 2 checks the head last, so with duplicates it removes the first match after the head. If you must remove the first match starting at the head, check the head first as in Way 1.
• The copy trick (copy head.next into the head, then delete head.next) also removes a value, but it changes which box holds which value. If other code holds a reference to those boxes, that is a bug.

What interviewers ask next

• Delete at a position instead of a key. Walk pos - 1 steps with prev (or reach the last box first when pos is the head) and rewire the same way.
• Delete a box when you are only handed that box, not the head. Copy the next box's value into it and skip the next box. That is O(1), but it fails for a one box ring and moves values around.
• Insert into a sorted circular list (LeetCode 708). Walk with prev and curr until the new value fits between them, or you hit the spot where the values drop from largest back to smallest.
• Why keep a pointer to the last box instead of the head? With last, the head is last.next, so you can add at the front and at the back in O(1).

Remember this

Grown-up words: the ring of kids is a circular singly linked list, the kid on the left is the previous node, holding hands over the gap is prev.next = curr.next, and checking every kid once is one traversal of the cycle.