Splitting a list into 2 lists

The lesson behind it is Making a sublist.

The method splitAlternate moves every second node out of a list and into a new list, then returns the new list. The list has no empty node in front of its first value (a sentinel), so head is the first real node, or null when the list is empty.

This device is not saving progress, so your checks will be gone when you reload.

The contract

public LinkedList splitAlternate()

What the class already has:

• private class Node with the fields data and next, and the constructor Node(Object data, Node next). This method never calls that constructor. Every node it uses already exists.
• private Node head is the first real node, or null.
• private int size counts the nodes. The method keeps it right on both lists.
• addFirst(Object data) puts a value at the front and adds 1 to size.
• toString() prints List size is: N, then 1 value per line from front to back.

Positions count from 0 (a 0 based position). The first node is at position 0 and the second node is at position 1. The nodes at the odd positions 1, 3, 5 and so on are the ones that move.

Moving nodes without building any

1. Make the new list first, empty, and call it other. Every path returns other, so the method never returns null.
2. Put keep on this.head. keep always sits on a node that stays.
3. Set tail to null. It will point at the last node of other (a tail pointer), so each moved node can go on the end.
4. Loop while keep and keep.next are both not null. The node after keep is the node that moves.
5. Save that node in moving. Then point keep.next past it. Now this list skips moving.
6. Set moving.next to null. This cuts the link from moving back into this list (to sever it).
7. Attach moving to other. It becomes other.head when other is empty, and goes after tail otherwise. Then tail moves to moving.
8. Add 1 to other.size and take 1 from this.size.
9. Step keep to keep.next. Since step 5 relinked it, that is the next node that stays.

public LinkedList splitAlternate() {
    LinkedList other = new LinkedList();
    Node keep = this.head;
    Node tail = null;
    while (keep != null && keep.next != null) {
        Node moving = keep.next;
        keep.next = moving.next;
        moving.next = null;
        if (tail == null) {
            other.head = moving;
        } else {
            tail.next = moving;
        }
        tail = moving;
        other.size++;
        this.size--;
        keep = keep.next;
    }
    return other;
}

The trace below runs the method once on a list that holds a b c d e, front to back.

At the end keep is on e, and e.next is null, so the loop stops. The 2 sizes add up to 5, the size before the call.

The cases

Each list is written front to back. Each case calls splitAlternate once and prints both lists.

• Empty and 1 node. The loop test fails on the first check, so nothing moves and other comes back empty. No if for these cases is needed.
• Odd length. The last node stays. Without the sever, d still points at e, and the returned list prints e as well.
• Even length. The last node moves. Then keep steps to null, which is why the loop test checks keep before keep.next.
• Equal values. The method moves by position. It never compares values.

The printed output of 4 of the cases, line for line. The label above each list comes from the test driver, not from toString.

Empty, this list:
List size is: 0
Empty, returned list:
List size is: 0

1 node, this list:
List size is: 1
a
1 node, returned list:
List size is: 0

5 nodes, this list:
List size is: 3
a
c
e
5 nodes, returned list:
List size is: 2
b
d

6 nodes, this list:
List size is: 3
a
c
e
6 nodes, returned list:
List size is: 3
b
d
f

Drill

Node moving = keep.next;
keep.next = moving.next;
if (tail == null) {
    other.head = moving;
} else {
    tail.next = moving;
}

Write it

if (tail == null) {
    other.head = moving;
} else {
    tail.next = moving;
}
tail = moving;

while (keep != null && keep.next != null)

Your checklist

Tick these when they are true.

• I make the new list on the first line and return it on every path, so the method never returns null.
• My method has no new Node in it. Every node it uses was already in the list.
• I save the node in moving before I point keep.next past it.
• I set moving.next to null, and I checked an odd length to prove it.
• A tail pointer puts each moved node on the end, so the new list keeps the old order.
• Each move adds 1 to the new list's size and takes 1 from this list's size, and the 2 sizes add up to the old size.
• My loop test covers the empty list, 1 node, an odd length and an even length with no extra if.

Could you write this cold?

Blank file, no notes, 4 hours on a clock, and only the Java API documentation open. Say yes only when that is true. You can take it back at any time.

The cutList problem in Practice exams 1 and 2 uses these moves.