5
\$\begingroup\$

Today, I tackled this coding question: Given a singly-linked list, check whether its length is even or odd in a single pass. An Empty list has 0 nodes which makes the number of nodes in it even.

Would the time complexity of my code be O(n)? Do you guys see any improvements that can be made?

public Boolean isListEven(ListNode head) {

    if(head == null){
        return true;
    }

    if(head.next.next == null){
        return false;
    }

    int count = 1;
    while(head.next != null){
        if(head.next.next != null){
            count = count + 2;
            head = head.next.next;
        }

        count = count + 1;
        head = head.next;
    }

    return (count % 2 == 0);
}
\$\endgroup\$
  • \$\begingroup\$ You can store the size of your list in an int. Everytime you insert an element or removing one you increese or decreese the size. If you then call this method, you have the value instantly. \$\endgroup\$ – Shinigami Mar 21 '17 at 5:04
6
\$\begingroup\$

The method signature is a bit odd, returning a Boolean object instead of a primitive boolean. A clearer name would be isListLengthEven(). The function could be static, since it does not rely on any object state.

If the list has one node, then your code will crash on if(head.next.next == null). In general, you should avoid cluttering your code with unnecessary special cases.

You don't need to keep track of count. This solution, like yours, is O(n), but it is much simpler:

public static boolean isListLengthEven(ListNode head) {
    for (; head != null; head = head.next.next) {
        if (head.next == null) return false;
    }
    return true;
}

The trick is to observe the loop invariant: each iteration through the loop, it advances head by two nodes, so that the picture at the top of the loop is always equivalent to the original. If it can't advance by two, then the list has an odd length.

\$\endgroup\$
  • \$\begingroup\$ Could you elaborate on your solution? How is it determining if the length is even or odd? Also I have never seen a semicolon at the beginning of a for loop, what is it's role in the solution? \$\endgroup\$ – TheLearner Mar 21 '17 at 16:24
  • \$\begingroup\$ @TheLearner I've added an explanation. A for loop has an initialization, test, and update field; the semicolon just indicates that nothing needs to be done for the initialization. \$\endgroup\$ – 200_success Mar 21 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.