this is my first question here. This may be a dumb question but I am having issues with understanding why the order specifically matters when reversing a linked list in this way. So here I'm reversing a linked list, which works

    ListNode prev = null, curr = head, next = head;
    
    while (curr != null){
        next = next.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;

which works just fine. But why can't I do the following?

//edge cases:
    if (head == null || head.next == null){
        return head;
    }
    
    ListNode prev = null, curr = head, next = head.next; //change here
    
    while (curr != null){
        //line was previously here
        curr.next = prev;
        prev = curr;
        curr = next;
        next = next.next; //moved here
    }
    head = prev;
    return head;

Why does it matter that I set next = next.next at the beginning of the while loop, rather than the end? Why can't I set next = head.next first and then iterate it at the end of the loop without getting a null pointer exception?

CodePudding user response：

Just for the record, you can think of the reverse operation as popping from the input list and pushing onto the result. Less epic code results:

ListNode reverse(ListNode head) {
  ListNode result = null;
  while (head != null) {
    ListNode elt = head;  // pop into elt
    head = head.next;
    elt.next = result;    // push elt onto result
    result = elt;
  }
  return result;
}

CodePudding user response：

When you make such a change, you change the state at which the loop condition will be verified. And this causes the issue.

In the working code, we have this loop invariant:

curr and next are equal. They are either both null or both reference the same node.

In the non-working code, this is not true, as now next is one step ahead. The corresponding loop invariant is now next == curr.next. So when curr is the tail node, next will be null. In the next iteration of the loop, next = next.next is executed, which is invalid as next was null, so this raises an exception.

It would work if you would make that statement conditional:

 if (next != null) next = next.next;

Or this would also work:

 if (next == null) break;
 next = next.next;

But both these alternatives are not as elegant as the original code, as now there are two checks to be made in each iteration (the loop condition, and this extra check). In fact, this extra check is just the repetition of the loop condition as at that moment next and curr are equal.