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!

Perfect time to fire up the debugger. Hint: have a close look at the value of `next`. — Henry, Aug 12 '17 at 10:30
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Aug 12 '17 at 10:47
Debugger is kind of a thing right now, I can't use one at the moment. Our learning enviroument is an online platform with only the exercise, a text field and the JUnit output. I'm currently on a friends PC to learn because I don't have access to mine. You helped me anyway! — lukstru, Aug 12 '17 at 11:26
If you can't install a decent IDE (e.g. Eclipse) on the PC you're using, look for online IDE's, develop your code there and then copy it to your "learning environment" - I hope your teachers don't forbid that. — Ralf Kleberhoff, Aug 12 '17 at 12:36
No they don't, and that's exactly what I did. Took me about an hour though to only find out what was wrong and fix it (move the `next = head.next()` one line down) Because ListElement isn't standard. I'm still a little slow on that side. But thanks y'all! I learned a few new things in progess. — lukstru, Aug 12 '17 at 15:32
[Please don't add "solved" to your question title](https://meta.stackexchange.com/questions/31809/putting-solved-in-the-title-of-a-question). Stack Overflow's answer acceptance mechanism takes care of identifying answered questions. — ChrisGPT was on strike, Sep 20 '17 at 02:27

score 1 · Accepted Answer · answered Aug 12 '17 at 13:32

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;
}

Revert singly-linked-list iterative inplace

1 Answers1