Why iteration linking works that way in Linked List

December 2, 2021

I cannot understand fully solution of 19th problem on Leetcode.

So when we created fast and slow – we created link of head? As I can judge yes. But then we iterate with fast – why it does not change head? I mean on every step we replace fast with fast.next? So somehow it doesn’t effect head and slow.

And then we replace slow.next with slow.next.next and it does effect head.

Could you please describe how it doesn’t replace nothing on first part and replace in the second.

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head

    for (let i = 0; i < n; i++) fast = fast.next // why it doesn’t change head and slow?

    if (!fast) return head.next

    while (fast.next) fast = fast.next, slow = slow.next
    slow.next = slow.next.next // why it change head?
    return head
 };

>Solution :

Assigning something to a variable will not mutate an object.

Assigning something to a property will mutate the object whose property you are setting.

In your case, fast is a variable, so assigning something to it like for example fast.next, will never mutate an object. It merely changes what fast is referencing.

On the other hand, slow.next is a property. Assigning something to that property will mutate the object that slow references.

Let’s visualise what fast = fast.next does. Let’s assume fast is the second node in a list of 3:

Before:

 head            fast 
  ↓               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: B   │   │ data: G   │   │ data: D   │
│ next: ──────> │ next: ──────> │ next: null│
└───────────┘   └───────────┘   └───────────┘

After:

 head                            fast 
  ↓                               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: B   │   │ data: G   │   │ data: D   │
│ next: ──────> │ next: ──────> │ next: null│
└───────────┘   └───────────┘   └───────────┘

Now look what slow.next = slow.next.next does. Let’s assume slow references the first node:

Before:

 slow
 head
  ↓  
┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: B   │   │ data: G   │   │ data: D   │
│ next: ──────> │ next: ──────> │ next: null│
└───────────┘   └───────────┘   └───────────┘

After:

 slow
 head
  ↓  
┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: B   │   │ data: G   │   │ data: D   │
│ next: ─────┐  │ next: ──────> │ next: null│
└───────────┘│  └───────────┘┌> └───────────┘
             └───────────────┘