Linked list applications and review

This week there is no new structure. You use the node skills you built in the first three weeks on the four algorithms most often asked on the exam: reversing a list, finding the middle, detecting a cycle and merging two sorted lists. All four run in O(n) time without using an extra array. At the end there is a summary comparing lists with arrays; for pre-midterm review, this page is enough.

Golden rules:

1. Before changing a reference, save the rest you need.
2. The two-reference technique (two pointers): one fast and one slow, or one ahead and one behind.
3. A dummy head node eliminates the checks “is the list empty, does the head change”.
4. Try every method in your head on an empty list and a single-element list.

Review: a summary of three weeks

* If there is room in the array. If it fills up, copying to a new array is O(n).

Reversing a list (reverse)

The idea: turn the arrow of every node backward. But the moment you change curr.next you can’t reach the rest of the list, so save it first.

static Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;   // 1) save the rest
        curr.next = prev;        // 2) flip the arrow
        prev = curr;             // 3) prev one step forward
        curr = next;             // 4) curr one step forward
    }
    return prev;
}

The state after each round on 1 2 3 4 (program output):

step 1: prev-list = 1 | curr = 2
step 2: prev-list = 2 1 | curr = 3
step 3: prev-list = 3 2 1 | curr = 4
step 4: prev-list = 4 3 2 1 | curr = null
4 3 2 1

PITFALL · writing return head. When the loop ends, the old head (1) is now the last node of the list and its next is null. The new head is prev. On the caller’s side, don’t forget to assign: head = reverse(head);.

The middle node: slow and fast references

Counting the length first and then walking n/2 steps is also a correct answer (two passes). To do it in a single pass, use two references: fast takes two steps while slow takes one. When fast reaches the end, slow is halfway.

static Node middle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

1..7 -> 4
1..6 -> 4
10 20 30 40 50 -> 30

With an even length there are two middles (3 and 4 for 1..6). With this loop condition it returns the second middle. If the question wants the first middle, change the condition to fast.next != null && fast.next.next != null.

Cycle detection (Floyd)

Faulty code may have accidentally linked the next of the last node to an earlier node. If you try to print this list, you get into an infinite loop. To tell whether there is a cycle with O(1) memory, the same slow/fast idea is used: of two people running on a track, if the track is circular, the faster one is bound to lap the slower one.

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Trace: 1 → 2 → 3 → 4 → 5 and 5 points back to 3.

step   slow   fast
 0      1      1
 1      2      3
 2      3      5
 3      4      4    (5 → 3 → 4)  they met → true

The program gave the same result: met after 3 steps, meeting node 4. In a 6-node list whose end is linked to the start, they meet at 1 after 6 steps.

TIP · Why is it bound to catch it? Once both are in the cycle, at each step the fast one advances one node more, so the distance between them shrinks by 1. When the distance drops to 0 they meet; they can’t jump over each other.

Merging two sorted lists (merge)

This operation is the heart of merge sort (week 14). Compare the fronts of the two lists, add the smaller to the result, and advance in that list.

static Node merge(Node a, Node b) {
    Node dummy = new Node(0), t = dummy;
    while (a != null && b != null) {
        if (a.data <= b.data) { t.next = a; a = a.next; }
        else                  { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;
    return dummy.next;
}

1 2 3 4 7 8 9
2 5 10 10 12 15
3 6

The third line is merge(null, 3 6): if one is empty the other is returned as it is. Without the dummy, you would have to pick the first element separately and make it the head; the dummy removes this special case. The result is dummy.next, not the dummy itself.

Using <= takes from a first when values are equal. This preserves the property we call stability in sorting algorithms.

Other two-reference patterns

The k-th element from the end. Move lead k steps ahead, then walk both together. When lead is null, trail is at the k-th node from the end. For 10 20 30 40 50 60 and k = 2 it is 50.

Removing duplicates in a sorted list. Skip an equal neighbour and don’t advance; advance if different. 1 1 2 3 3 3 4 → 1 2 3 4.

Swapping in pairs. Skip two at a time with p = p.next.next and swap data. 1 2 3 4 5 → 2 1 4 3 5.

List or array?

Rule: if there is a lot of random access, an array; if there is a lot of insertion/deletion at the front or middle, a list.

Common mistakes

static Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;   // save the rest
        curr.next = prev;        // flip the arrow
        prev = curr;             // one step forward
        curr = next;
    }
    return prev;                 // the new head
}

Node slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow;

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;   // the same NODE (==), not the same data
    }
    return false;
}

static Node merge(Node a, Node b) {
    Node dummy = new Node(0), t = dummy;
    while (a != null && b != null) {
        if (a.data <= b.data) { t.next = a; a = a.next; }
        else                  { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;   // the leftover list
    return dummy.next;
}

Node p = head;
while (p != null && p.next != null) {
    if (p.data == p.next.data) p.next = p.next.next;
    else p = p.next;
}
print(head);

Node lead = head, trail = head;
for (int i = 0; i < k; i++) lead = lead.next;
while (lead != null) { lead = lead.next; trail = trail.next; }
return trail.data;

for (Node p = head; p != null && p.next != null; p = p.next.next) {
    int t = p.data;
    p.data = p.next.data;
    p.next.data = t;
}
print(head);

Node x = build(3, 6, 9);
x = reverse(x);
Node y = build(1, 5);
Node z = merge(y, reverse(x));
System.out.println(str(z) + " middle=" + middle(z).data);