I am working with code that is to rearrange a linked list, such that nodes are taken from the front and back of the list in alternating fashion, and so convert a list of 1->2->3->4->5->6 to 1->6->2->5->3->4.

This is the code for rearranging a given linked list in-place:

class LinkedList {
    static Node head; // head of the list

    /* Node Class */
    static class Node {
        int data;
        Node next;
        // Constructor to create a new node
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    void printlist(Node node)
    {
        if (node == null) {
            return;
        }
        while (node != null) {
            System.out.print(node.data   " -> ");
            node = node.next;
        }
    }

    Node reverselist(Node node)
    {
        Node prev = null, curr = node, next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        node = prev;
        return node;
    }

    void rearrange(Node node)
    {
        // 1) Find the middle point using tortoise and hare
        // method
        Node slow = node, fast = slow.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2) Split the linked list in two halves
        // node1, head of first half 1 -> 2 -> 3
        // node2, head of second half 4 -> 5
        Node node1 = node;
        Node node2 = slow.next;
        slow.next = null;
        // 3) Reverse the second half, i.e., 5 -> 4
        node2 = reverselist(node2);
        // 4) Merge alternate nodes
        node = new Node(0); // Assign dummy Node
        // curr is the pointer to this dummy Node, which
        // will be used to form the new list
        Node curr=node;
        while (node1 != null || node2 != null) {
            // First add the element from first list
            if (node1 != null) {
                curr.next = node1;
                curr = curr.next;
                node1 = node1.next;
            }
            // Then add the element from second list
            if (node2 != null) {
                curr.next = node2;
                curr = curr.next;
                node2 = node2.next;
            }
        }
        // Assign the head of the new list to head pointer
        node = node.next;
    }

    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(5);
        list.head.next.next.next.next.next = new Node(6);
        list.printlist(head); // print original list
        list.rearrange(head); // rearrange list as per ques
        System.out.println("");
        list.printlist(head); // print modified list
    }
}

My question is about this section of the code:

Node curr=node;
while (node1 != null || node2 != null) {
    // First add the element from first list
    if (node1 != null) {
        curr.next = node1;
        curr = curr.next;
        node1 = node1.next;
    }
    // Then add the element from second list
    if (node2 != null) {
        curr.next = node2;
        curr = curr.next;
        node2 = node2.next;
    }
}

I debugged this in VScode, and I see that when curr is pointing to node the statement curr.next=node1 creates a change in node. But when doing curr=curr.next no changes are made to node. Why is that happening?

CodePudding user response：

curr is point to node and when curr.next=node1 it also create change in node but when curr=curr.next it does not make any changes in node

The only way to make a change to an object, is to assign somehow to properties of that object. This is what curr.next=node1 does: it assigns something to an object's next property.

On the other hand, an assignment to a variable will never change an object. It merely changes the content of a variable. That is what curr=curr.next does.

It may help to visualise it. Let's say we have node after the first loop (in a list with just one node)

node
 ↓
┌────────────┐
│ data: 1    │ 
│ next: null │ 
└────────────┘

Then Node node1 = node; creates a new reference to the same node:

node  node1
 ↓     ↓
┌────────────┐
│ data: 1    │ 
│ next: null │ 
└────────────┘

A bit later, we create a new node with node = new Node(0);:

node             node1
 ↓                ↓
┌────────────┐   ┌────────────┐
│ data: 0    │   │ data: 1    │
│ next: null │   │ next: null │ 
└────────────┘   └────────────┘

When Node curr=node; executes, we merely get a variable that references the same node as node:

node  curr       node1
 ↓     ↓          ↓
┌────────────┐   ┌────────────┐
│ data: 0    │   │ data: 1    │
│ next: null │   │ next: null │ 
└────────────┘   └────────────┘

When curr.next=node1 is executed, the next property of the object is set to reference the object that node1 is referencing. So:

node  curr       node1
 ↓     ↓          ↓
┌────────────┐   ┌────────────┐
│ data: 0    │   │ data: 1    │
│ next: ────────►│ next: null │ 
└────────────┘   └────────────┘

But when curr=curr.next is executed, no object is mutated. This assigns to a variable, and that only affects that variable, not what it references:

node             curr  node1
 ↓                ↓     ↓
┌────────────┐   ┌────────────┐
│ data: 0    │   │ data: 1    │
│ next: ────────►│ next: null │ 
└────────────┘   └────────────┘

I hope this clarifies the difference.