Split a Circular linked list into two halves

The problem, simply

You get a circular linked list: a chain of boxes where the last box points back to the first one, so there is no null at the end.

Split it into two circular lists of half the size each. If the number of boxes is odd, the first ring gets one extra box. Give back the heads of both rings.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count first, then cut.

1. Walk around the ring once and count the boxes, n.
2. The first ring gets (n + 1) / 2 boxes. Walk that many minus one steps from the head to find tail1.
3. head2 = tail1.next. Walk from head2 until the box whose next is the old head. That is tail2.
4. Close both rings: tail1.next = head1 and tail2.next = head2.

class Solution {
    public ListNode[] split(ListNode head) {
        if (head == null || head.next == head) return new ListNode[] { head, null };
        int n = 1;
        for (ListNode cur = head.next; cur != head; cur = cur.next) n++;   // count once around
        ListNode tail1 = head;
        for (int i = 1; i < (n + 1) / 2; i++) tail1 = tail1.next;
        ListNode head2 = tail1.next;
        ListNode tail2 = head2;
        while (tail2.next != head) tail2 = tail2.next;                     // the box before head
        tail1.next = head;      // close the first ring
        tail2.next = head2;     // close the second ring
        return new ListNode[] { head, head2 };
    }
}

How long it takes: one full lap to count and about one more lap to find the cut and the tail, so O(n). Extra room: O(1).

Way 2: the clever way

Use two runners on the ring: slow moves one box per turn, fast moves two.

1. Both start at the head.
2. Keep going while fast.next and fast.next.next are not the head.
3. When they stop, slow is the end of the first half. If the ring is even, fast is one box short of the tail, so move it one more step. Now fast is the last box of the ring.
4. head2 = slow.next. Close the rings: slow.next = head and fast.next = head2.

For an even ring like 1 2 3 4, the loop stops with slow on 2 and fast on 3, because fast.next.next is the head. That is the case where fast takes one more step, to 4, before closing the rings.

class Solution {
    public ListNode[] split(ListNode head) {
        if (head == null || head.next == head) return new ListNode[] { head, null };
        ListNode slow = head, fast = head;
        while (fast.next != head && fast.next.next != head) {
            slow = slow.next;            // one step
            fast = fast.next.next;       // two steps
        }
        if (fast.next.next == head) fast = fast.next;   // even ring: reach the last box
        ListNode head2 = slow.next;
        slow.next = head;                // close the first ring
        fast.next = head2;               // close the second ring
        return new ListNode[] { head, head2 };
    }
}

How long it takes: fast goes around the ring once, O(n). Extra room: O(1). It reads each box about once instead of twice.

Watch out for

• The even case: without the extra step, fast is not the last box, and closing the second ring drops a box.
• The one box ring: head.next == head. Return it with an empty second ring before running the loop.
• Close the second ring with the old tail, not with head. If the old tail still points to head, the two rings stay glued together.

What interviewers ask next

• Why do two runners find the middle? fast covers twice the distance of slow, so when fast has done nearly a full lap, slow has done half.
• Second ring bigger when odd? Change the stop rule so slow stops one box earlier, or move slow back by one with a trailing finger.
• Split a normal (not circular) list into halves? Same runners, stop on null instead of head. This is the first step of merge sort on a list.
• Check if a list is circular at all? Walk from the head. If you reach null, it is not. If you get back to head, it is. For a loop that does not go back to the head, use the slow and fast runners.

Remember this

Grown-up words: the ring is a circular linked list, the two runners are the fast and slow pointer technique (also called the tortoise and the hare), and the boxes are nodes.