I am solving a challenge from hackerrank. This is the description of the question.

import java.io.*;
import java.util.*;

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {

    public static  Node insert(Node head,int data) {
        //Complete this method        
    }

    public static void display(Node head) {
        Node start = head;
        while(start != null) {
            System.out.print(start.data   " ");
            start = start.next;
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Node head = null;
        int N = sc.nextInt();

        while(N-- > 0) {
            int ele = sc.nextInt();
            head = insert(head,ele);
        }
        display(head);
        sc.close();
    }
}

It is basically implementing a Linked List, and I eventually did solve the problem. However I have some question about the code.

This is the correct code which gives the desired output:

    public static  Node insert(Node head,int data) {
        if (head == null) {
        head = new Node(data);
    } else {
        Node current = head;
        while(current.next != null)
            current = current.next;
        current.next = new Node(data);
    }
    return head;
    }

This is the incorrect code I wrote at first:

    public static  Node insert(Node head,int data) {
        if (head == null) {
            head = new Node(data);
        } else {
            Node current = head;
            while(current != null)
                current = current.next;     
            current = new Node(data);
        }        
        return head;
    }

The difference is the the while loop statement and the code after while loop. When running the entire java code, using the sample input, the incorrect code only output 2, where the expected output being 2 3 4 1

I am guessing it is something about the pointer reference? But when I break the code into steps, the incorrect code still seems reasonable to me.

• the correct code, current stays on head before it creates new node with data.
• the incorrect code, current goes to head.next before it creates new node with data.

I draw out the steps of the code (upper is the correct code, below is incorrect code), and end up with two question:

1. Is the incorrect code wrong because what I circled in the image? like I cannot create a node when I am at null? (if that is the case, why no exception error then?)
2. Another things that bothers me is that the code I underline in the image seem equivalent.

Can someone point out why the incorrect code cannot give the desired output? Thank you!

CodePudding user response：

    current = new Node(data);

If current is null, this is effectively

null = new Node(data);

which is an error and does not link your list.

null is not the end of your list, the node that points to null is the end (not null).

And you have to find and hold onto that.

CodePudding user response：

This statement:

current = new Node(data);

...does not mutate the list. It just stores a new node in a variable. But the list is not influenced by that assignment. In order to add a node to a non-empty list, you'll have to update the next attribute of a node, more particularly, the tail node. But the important difference here is between assigning to a local variable (does not influence a list), and to an attribute of a node that is already in the list (that does influence the list).

So the job of the code must be to find the tail node. That is what the loop is for. The wrong code, overshoots the last node, and so there is no reference to the tail node when the loop exits. And so -- empty handed -- there is no way to assign the new node to a next attribute of the tail node.