Find the minimum gap (difference) between adjacent elements in a linked list

Question

Write a method called minGap that returns the minimum gap between adjacent values in a list of integers. The gap between two adjacent values in a list is defined as the second value minus the first value. For example, suppose a variable called list stores these values:

[1, 3, 6, 7, 12]

The first gap is 2 (3 - 1), the second gap is 3 (6 - 3), the third gap is 1 (7 - 6), and the fourth gap is 5 (12 - 7). Thus, the call:

list.minGap()

should return 1 because that is the smallest gap. Notice that the minimum gap could be a negative number. For example, if list stores the following:

[3, 5, 11, 4, 8]

The gaps are 2 (5 - 3), 6 (11 - 5), -7 (4 - 11), and 4 (8 - 4). Of these values, -7 is the smallest, so it would be returned.

Your method should return 0 if the list has fewer than 2 elements. You are writing a method for the LinkedIntList class:

    public class ListNode {
        public int data;       // data stored in this node
        public ListNode next;  // link to next node in the list

        <constructors>
    }

    public class LinkedIntList {
        private ListNode front;

        <methods>
    }

Your method should not modify the list contents and is required to run in O(n) time where n is the length of the list. You may not call any other methods of the LinkedIntList class and you may not construct any structured objects to solve this problem.

I'm unsure if I'm doing the right thing for checking minimums by setting the int minGap to Integer.MAX_VALUE (let me know if this is bad). I want to get better at these problems, so any tips that can make my code more readable or easier to write would be awesome! I didn't know a lot about using multiple references to linked lists before I solved this problem, so any advice to solving these problems in the future would be much appreciated.

public int minGap() {
    if (front == null || front.next == null) {
        return 0;
    }
    int minGap = Integer.MAX_VALUE;
    ListNode prev = front;
    ListNode p = front.next;
    while (p != null) {
        int checkGap = p.data - prev.data;
        if (checkGap < minGap) {
            minGap = checkGap;
        }
        prev = p;
        p = p.next;
    }
    return minGap;
}

Answer 1

You don't need to store the whole previous node, just the value. Also, you can replace checking whether the gap is smaller with min, although it's mainly a matter of taste. And p is a rather opaque variable name

public int minGap() {
    if (front == null || front.next == null) {
        return 0;
    }
    int minGap = Integer.MAX_VALUE;
    int lastValue = front.data;
    ListNode currentNode = front.next;
    while (currentNode != null) {
       minGap = min(minGap, currentNode.data-lastValue);
       lastValue = currentNode.value;
       currentNode = currentNode.next;
    }
    return minGap;
}

Answer 2

Since you already checked that front.next is non-null, you could rearrange your initializations and initialize minGap to:

...
ListNode prev = front;
ListNode p = front.next;
int minGap = p.data - prev.data;
...

This would make the first iteration of the loop mostly redundant, but ensures minGap is always a valid gap value.

Answer 3

You could initialize it to the "error out" value, then use another variable to force it to replace it on the first loop iteration. Also, since it is initialized to the "error out" value, you can skip one of the error check conditions.

public int minGap() {
    int minGap = 0;
    int firstCheck = 1;

    ListNode prev = front;
    if (prev == null) { return minGap; }

    ListNode p = front.next;
    while (p != null) {
        int checkGap = p.data - prev.data;
        if (checkGap < minGap || firstCheck == 1) {
            minGap = checkGap;
            firstCheck = 0;
        }
        prev = p;
        p = p.next;
    }

    return minGap;
}

In this arrangement, we are checking both prev and p for null immediately after assigning to them, so it is a little easier to keep the null check consistent (for instance if front.next gets refactored to some other name, you have two places to change it, rather than three).