Revert singly-linked-list iterative inplace

Question

I am learning for an upcoming exam and we have the following exercise:

Revert a singly-linked-list by the following rules:

• Iterative
• Inplace
• no Constructors
• last Element always has null as next Element

I already found a few solutions and have come up with my own:

public ListElement<T> revert(ListElement<T> head)
{
    if(head == null)
    return null;

    ListElement<T> prev = null;
    for(ListElement<T> next = head.next(); head.hasNext(); head = next){
        head.setNext(prev);
        prev = head;
    }

    return head;
}

but our testing framework (Only gives JUnit feedback) does not give me more information than this:

Testheadder – testReverseStatic_correct_inplace(singly_linked_list.reverse.test_reverse_iterative.TestReverseList)

Message – test timed out after 30 milliseconds

What did I do wrong?

Thanks in advance!

Answer 1

In your implementation, the value of next never changes:

ListElement<T> prev = null;
for(ListElement<T> next = head.next(); head.hasNext(); head = next){
    head.setNext(prev);
    prev = head;
}

It is a desirable programmer skill to be able to debug such simple problems on paper. It's important to practice this. You can write a table with the variables and their state changes with every instruction, for example, given the initial state of a linked list of 1 -> 2 -> 3 -> null:

head = 1 -> 2 -> 3 -> null
prev = null

The variables will go through the following states with each instruction:

step               | prev           | head                | next
start              | null           | 1 -> 2 -> 3 -> null | null
next = head.next() | null           | 1 -> 2 -> 3 -> null | 2 -> 3 -> null
head.setNext(prev) | null           | 1 -> null           | 2 -> 3 -> null
prev = head        | 1 -> null      | 1 -> null           | 2 -> 3 -> null
head = next        | 1 -> null      | 2 -> 3 -> null      | 2 -> 3 -> null
head.hasNext() => true
head.setNext(prev) | 1 -> null      | 2 -> 1 -> null      | 2 -> 1 -> null
prev = head        | 2 -> 1 -> null | 2 -> 1 -> null      | 2 -> 1 -> null
head = next        | 2 -> 1 -> null | 2 -> 1 -> null      | 2 -> 1 -> null
head.hasNext() => true
head.setNext(prev) | 2 -> 2 -> ...  | 2 -> 2 -> ...       | 2 -> 2 -> ...
prev = head        | 2 -> 2 -> ...  | 2 -> 2 -> ...       | 2 -> 2 -> ...
head = next        | 2 -> 2 -> ...  | 2 -> 2 -> ...       | 2 -> 2 -> ...
head.hasNext() => true
...

By 2 -> 2 -> ... I mean that 2 points to 2 itself, a never ending cycle. Once this cycle is reached, we have an infinite loop. It's all because next never changes, and so the implementation stops making progress.

Here's one possible fix:

public ListElement<T> reverse(ListElement<T> head) {
  ListElement<T> prev = null;
  for (ListElement<T> node = head; node != null; ) {
    ListElement<T> next = node.next();
    node.setNext(prev);
    prev = head = node;
    node = next;
  }

  return head;
}