The following code results in an "Error - Found cycle in the ListNode" error

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode current = head.next;
        while (current != null) {
            //move current to front of list
            ListNode temp = current.next;
            current.next = head;
            head = current;
            current = temp;
        }
        return head;
    }

Yet the following code works fine:

public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null) {
            //move current to front of list
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

To me the code looks like it would do the same thing but instead of prev they use head. Ideas why it is different?

CodePudding user response：

The faulty code does not ever change the next member of the first node. Thus a cycle will be created between the first two nodes, which will become the last two nodes once the list has been reversed. It may help to visualise it with an example list having 1, 2 and 3 as node values:

The state when the loop is about to start its first iteration:

 head             current
  ↓                ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value:   1 │   │ value:   2 │   │ value:   3 │
│ next: ────────►│ next: ────────►│ next: null │
│            │   │            │   │            │
└────────────┘   └────────────┘   └────────────┘

Effect of ListNode temp = current.next;:

 head             current          temp
  ↓                ↓                ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value:   1 │   │ value:   2 │   │ value:   3 │
│ next: ────────►│ next: ────────►│ next: null │
│            │   │            │   │            │
└────────────┘   └────────────┘   └────────────┘

Effect of current.next = head;:

 head             current          temp
  ↓                ↓                ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value:   1 │   │ value:   2 │   │ value:   3 │
│ next: ────────►│ next: ─┐   │   │ next: null │
│            │◄───────────┘   │   │            │
└────────────┘   └────────────┘   └────────────┘

... the cycle is made!

The next two statements head = current; and current = temp; only move references:

                  head             current
                   ↓                ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value:   1 │   │ value:   2 │   │ value:   3 │
│ next: ────────►│ next: ─┐   │   │ next: null │
│            │◄───────────┘   │   │            │
└────────────┘   └────────────┘   └────────────┘

The next iteration will not touch this cycle anymore. The damage is permanent. The returned list will be:

                                   head
                                    ↓
┌────────────┐   ┌────────────┐   ┌────────────┐
│ value:   1 │   │ value:   2 │   │ value:   3 │
│ next: ────────►│ next: ─┐   │   │ next: ─┐   │
│            │◄───────────┘   │◄───────────┘   │
└────────────┘   └────────────┘   └────────────┘