Reversing second half of linked list

Question

I recently had an interview where I was asked to reverse the second half of a linked list. The driver program was unknown to me, I just needed to write the method to do this. The method was supposed to behave as follows:

• 1 -> 2 -> 3 -> 4 becomes 1 -> 2 -> 4 -> 3

• 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 5 -> 4 -> 3

  The function signature was as follows:

public static void reverseList(ListNode node)

I don't remember verbatim the code I submitted, but I wrote something up that follows very closely to what I submitted. The code follows:

public static void reverseList(ListNode node) {
    if(node == null) return;
    int size = size(node);
    if(size == 1) return;
    int i = 0;
    ListNode middleOfList = null;
    ListNode currentNode = node;
    //traverse the first half of the list
    while(i < size/2) {
        middleOfList = currentNode;
        currentNode = currentNode.getNext();
        i++;
    }
    ListNode previous = null;
    //reverse the second half of the list
    while(currentNode != null) {
        ListNode next = currentNode.getNext();
        currentNode.setNext(previous);
        previous = currentNode;
        currentNode = next;
    }
    //reattach first and second halves of the list
    middleOfList.setNext(previous);
}

public static int size(ListNode node) {
    ListNode current = node;
    int count = 0;
    while(current != null) {
        count++;
        current = current.getNext();
    }
    return count;
}

While I don't think this is a terrible approach for an internship interview, I'm nervous because the solution seems to be \$O(n^2)\$ since I first traverse the entire list to get the size and then traverse it again to do the actual reversal.

Is there a more efficient solution? Any general feedback on style is also appreciated.

Answer 1

Complexity analysis

the solution seems to be O(n^2) since I first traverse the entire list to get the size and then traverse it again to do the actual reversal.

That's not \$\mathcal{O}(n^2)\$. That's \$\mathcal{O}(n)\$, because \$n + n\$ is still \$\mathcal{O}(n)\$. It would be quadratic time if you traversed the entire list \$n\$ times because \$n \cdot n\$ is \$\mathcal{O}(n^2)\$. But you only do so twice. For complexity analysis, twice is no different from once. We only care about things that vary with the input size.

If you said this to them, this is a potential interview fail.

Using for loops for iteration

public static int size(ListNode node) {
    ListNode current = node;
    int count = 0;
    while(current != null) {
        count++;
        current = current.getNext();
    }
    return count;
}

It doesn't make any functional difference, but consider

public static int size(ListNode node) {
    int count = 0;
    for (ListNode current = node; current != null; current = current.getNext()) {
        count++;
    }

    return count;
}

Now we can easily see that for every node in the list, we want to increment count. It even gets the scope right. The count can be seen outside the loop, but current can't. We don't need it after the loop, and it is gone. We do need count, and it is still there to be returned.

This puts all the loop definition in one line. The original spreads it throughout the method.

I also added a bit of extra whitespace for readability.

Know your exit conditions

    if(node == null) return;
    int size = size(node);
    if(size == 1) return;

You can write this more briefly as

int size = size(node);
if (size < 2 * 2) {
    return;
}

You don't need to check if node is null, as the size check will handle that for you. You also don't to check lists of size 2 or 3. Such lists won't be any different, as the second half of the list is only one element long.

I prefer to always use the block form of control structures rather than the statement form. Some prefer the way that you did it. This is something that could potentially fail an interview, so try to determine their attitude before picking a style.

I would put a blank line after this section to separate it from the rest of the method.

Don't duplicate work

    ListNode middleOfList = null;
    ListNode currentNode = node;
    //traverse the first half of the list
    while(i < size/2) {
        middleOfList = currentNode;
        currentNode = currentNode.getNext();
        i++;
    }

Consider

    ListNode middle = null;
    for (size /= 2; size > 0; size--) {
        middle = middle.getNext();
    }

    ListNode current = middle.getNext();

Now, instead of updating two variables each time, we update one. Then we set the second once, after the loop is done.

We get rid of i altogether. But at the cost of a misleading value for size. Perhaps replace size with i or remaining or similar.

A reverse method

    middleOfList.setNext(previous);

Consider what you would have to do to replace that with

    middle.setNext(reverse(middle.getNext()));

Then you'd have another general purpose algorithm like size that could be reused elsewhere.

Evaluating

I would consider this a reasonable solution. Perhaps you could make slight performance tweaks, but you generally shouldn't need to do so. You have to traverse the list at least once, so it's going to be linear time. Your version is still linear time. Your size method is well contained and reusable.

You are not thread safe (consider what happens if another thread cuts the list by two thirds after you get the size but before you find the middle), but it's not evident that you need to be.

Other than that and the two potential failing issues, my only other comment is that I'd prefer more paragraphing in the code. Separate the method into code blocks with blank lines between.

I personally would put a space between control structures like if and while and the following open parenthesis. But in interviewing, try to determine their style and match it with your code. If they do it the way that I do, then match them. If they do it the way that you do, then just do it how you normally would.