0

I’m attempting to reverse a singly linked list in Java, but I'm running into confusion about how references work during the reversal process. Specifically, I don’t understand why setting the next pointer of a node to null doesn’t affect the node that it was pointing to (i.e., the node after it).

Here’s an example to illustrate the problem:

Example: Consider the following initial linked list:

1 -> 2 -> 3 -> null

In the first iteration of the loop, node 1’s next points to node 2. I am using the following code to reverse the list:

class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode temp = head; while (temp != null) { ListNode front = temp.next; // Save next node (which is node 2 initially) temp.next = prev; // Set node1.next to null (disconnect node1 from node2) prev = temp; temp = front; } return prev; } }

What I expect to happen: Initially, node 1's next points to node 2. In the first iteration, when I set node1.next = null, I expect node 2 itself to somehow be affected — either its next pointer should become null, or node 2 itself should become null. What actually happens: After setting node1.next = null, the list becomes:

1 -> null 2 -> 3 -> null

Node 2 remains unaffected, and its next pointer is still pointing to node 3. Node 2 itself is not nullified.

My confusion: Why doesn’t node 2 become null when I set node 1’s next pointer to null? I expected that disconnecting node 1 from node 2 would also somehow affect node 2 (perhaps by nullifying its next or even nullifying the node itself), but this doesn’t happen.

Example with Front Pointer: Let me explain this confusion with a related example:

When I perform front = temp.next, this saves the reference to the next node (i.e., in the first iteration, front will be pointing to node 2 because temp is node 1). This is valid, and node 2 is now the front reference.

However, when I perform temp.next = prev; (i.e., setting node1.next = null), only node 1’s next pointer is updated. It doesn’t affect node 2, even though in the front = temp.next step, node 1’s next was pointing to node 2.

Why is it that when I set node1.next = null, only node 1’s next pointer is updated, but not node 2’s next (or node 2 itself)?

What I don’t understand: Why doesn’t setting node1.next = null also affect the node that node1.next was pointing to (i.e., node 2)? If front can correctly hold a reference to node 2 when saving temp.next, why doesn’t node 2 itself become null (or its next pointer be modified) when setting node1.next = null?

Improve this question
2
  • 7
    Suppose I'm pointing my finger at Jeremy over there, and then I stop pointing at Jeremy and put my hand in my pocket. Is that going to do anything to Jeremy, or his finger? Commented Feb 3 at 19:25
  • @user2357112 When I perform front = temp.next, this saves the reference to the next node (i.e., in the first iteration, front will be pointing to node 2 because temp is node 1). This is valid, and node 2 is now the front reference. Why doesn't just the node1's next pointer get assigned to front instead of node 2 going by the same logic? Commented Feb 3 at 19:59

3 Answers 3

Reset to default
5

It may help to visualise your example list like a kind of memory layout. When the first statement inside the loop has executed (front = temp.next), we have this state:

 ┌──────┐ prev: │ null │ └──────┘ ┌──────┐ front:│ ──────────────────────────────┐ └──────┘ │ ┌──────┐ │ head: │ ─┐ │ │ └───│──┘ ┌───────┬──────┐ │ ┌───────┬──────┐ ┌───────┬──────┐ └──────────►│ val: │ 1 │ └►│ val: │ 2 │ │ val: │ 3 │ ┌──────────►├───────┼──────┤ ├───────┼──────┤ ├───────┼──────┤ │ │ next: │ ───────►│ next: │ ───────►│ next: │ null │ ┌───│──┐ └───────┴──────┘ └───────┴──────┘ └───────┴──────┘ temp: │ ─┘ │ └──────┘

Boxes with values (like 1, 2, 3, null or references) represent pieces of allocated memory. Note how the assignment to front did not make front an alias for temp.next. No, it has its own memory (box), and the value it received is a copy of the value that is in temp.next, so that now we have two references to the second node. They are each stored in their own memory location and future assignments may make that they no longer have the same reference.

Now to temp.next = null. This indeed disconnects the first node. Note that the assignment is to the next field of the first node. That is a specific memory location, which -- before the assignment executes -- has a reference to the second node. It is that and only that memory location that is the target of the assignment, and so the result can be depicted as follows:

 ┌──────┐ prev: │ null │ └──────┘ ┌──────┐ front:│ ──────────────────────────────┐ └──────┘ │ ┌──────┐ │ head: │ ─┐ │ │ └───│──┘ ┌───────┬──────┐ │ ┌───────┬──────┐ ┌───────┬──────┐ └──────────►│ val: │ 1 │ └►│ val: │ 2 │ │ val: │ 3 │ ┌──────────►├───────┼──────┤ ├───────┼──────┤ ├───────┼──────┤ │ │ next: │ null │ │ next: │ ───────►│ next: │ null │ ┌───│──┐ └───────┴──────┘ └───────┴──────┘ └───────┴──────┘ temp: │ ─┘ │ └──────┘

To be clear: that assignment has nothing to do with the memory that is named "front", nor with the memory allocated for the second node. Those are difference memory locations that are distinct from the memory that is holding the value of the next field of the first node.

I hope this clarifies why it works like that.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Great explanation! By the way, did you make all those diagrams by hand or did you use a tool?
By hand, but with the help of keyboard keys mapped to those characters and some copy/paste.
1

Look at your ListNode class. Notice each node has its own value and a next value, but not a previous value. When you change the value of 1's next node, you're not changing any value of node 2.

Improve this answer

1 Comment

When I perform front = temp.next, this saves the reference to the next node (i.e., in the first iteration, front will be pointing to node 2 because temp is node 1). This is valid, and node 2 is now the front reference. Why doesn't just the node1's next pointer get assigned to front nstead of node 2 going by the same logic?
0

Your code has two small problems, the first is that the while condition prevents the last operation from being executed, which is absolutely necessary, to set the next node to the one that was previously the last node, that is:

temp.next = prev;

without this line, the node, which now becomes the “head”, is left with a null “next”.

The other problem, is that your method returns the wrong node, it should return the one that previously was the last one (that happens to be head), we can correct it like this:

public ListNode reverseList( ListNode head ) { ListNode prev = null; ListNode temp = head; while( true ) { // we remove the “while” condition and set this “if”, which allows us to // execute the missing line, and exit the loop if( temp.next == null ) { temp.next = prev; break; } ListNode front = temp.next; temp.next = prev; prev = temp; temp = front; } // we return the correct node return temp; }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.