I'm studying data structures in Javascript to prep for interviews and am a bit stumped by a return value in the solution. Details below.

The Problem (Reference Link): https://www.hackerrank.com/challenges/delete-a-node-from-a-linked-list/problem

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value.

Boilerplate:

const SinglyLinkedListNode = class {
    constructor(nodeData) {
        this.data = nodeData;
        this.next = null;
    }
};

const SinglyLinkedList = class {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    insertNode(nodeData) {
        const node = new SinglyLinkedListNode(nodeData);

        if (this.head == null) {
            this.head = node;
        } else {
            this.tail.next = node;
        }

        this.tail = node;
    }
};

function printSinglyLinkedList(node, sep, ws) {
    while (node != null) {
        ws.write(String(node.data));

        node = node.next;

        if (node != null) {
            ws.write(sep);
        }
    }
}

And the functional answer:

/*
 * Complete the 'deleteNode' function below.
 *
 * The function is expected to return an INTEGER_SINGLY_LINKED_LIST.
 * The function accepts following parameters:
 *  1. INTEGER_SINGLY_LINKED_LIST llist
 *  2. INTEGER position
 */


/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode next;
 * }
 *
 */

function deleteNode(llist, position) {
    
    let head = llist
    let currentNode = head
    let count = 1
    
    if (head === null) return;
    if (position === 0){ 
        head = head.next
        return head
  
    if (currentNode === null || currentNode.next === null) return;
    while (count < position){
        count  
        currentNode = currentNode.next   
    }
    currentNode.next = currentNode.next.next
    return head
    }

This function appears to pass all tests provided.

My question is: Why does returning 'head' give me the correct answer? It does not appear that head is being altered in the function. Returning llist also gives a correct answer as well.

I've tried returning currentNode but obviously that provides the values from currentNode on.

CodePudding user response：

Why does returning 'head' give me the correct answer?

Because head is a reference to a node. It is only because that node itself also has a reference to a next node, and that next node might also have a reference to a next node, that this head reference implies a linked list. Even though the node that head references might remain the same node, somewhere along that chain of next references, there might be a change (and will be), and so implicitly the head reference leads to a linked list that is no longer the same.

It does not appear that head is being altered in the function.

Unless it is the head node itself that needs to be removed, this is a true statement. That is because head only references the first node. So if the first node has to stay in the linked list, head does not need to change. What will change is a next reference somewhere along the way.

Returning llist also gives a correct answer as well.

Yes, the introduction of the variable head is actually overkill. We can solve this without that extra variable and just use llist where this code uses head.

It may help to visualise this.

Let's say we have a linked list with four nodes (with values 1, 2, 3 and 4) and position is 2. Then when the code execution arrives at the while statement, we have this state:

llist
head  currentNode
  ↓      ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

As position is 2, the purpose of this code is to remove the node with value 3 from this list.

The while loop will make one iteration in this case, so that currentNode will reference the predecessor of the node that needs to be removed:

llist
head             currentNode
  ↓                ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

The first statement after the while loop performs a "redirection" of the next reference that is stored in that predecessor node:

llist
head             currentNode
  ↓                ↓           ┌────────────────┐
┌───────────┐    ┌───────────┐ │  ┌───────────┐ │  ┌───────────┐
│ value: 1  │    │ value: 2  │ │  │ value: 3  │ └> │ value: 4  │
│ next: ───────> │ next: ──────┘  │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

Note that there is nothing anymore that references the node with value 3. It has become unreachable to any JavaScript code. The garbage collector can free its memory, so the above is no different from this:

llist
head             currentNode
  ↓                ↓           
┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 4  │
│ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘ 

In all this process, head did not change. The change is reflected in one of the nodes that is in the chain of next references, and so we could say the linked list was mutated.

I hope this clarifies how it works.