Appending a node to end of tail with Java

Question

I am working on a basic Hackerrank problem where we append an element to the end of the linked list.

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/
Node Insert(Node head,int data) {
    if(head == null) {
        Node node = new Node();
        head = node;
        head.data = data;
        head.next = null;
        return head;
    }

    while(head != null) {
        head = head.next;
    }

    head.data = data;
    head.next = null;
    return head;
}

For some reason, this solution does not compile. I was looking problems other people solved, and they used a temporary node in the non-empty linked list solutions.

Yeah so now `head.data = data;` will throw the NPE (at the end). But anyway, if your solution does not compile, what's the error message ? — Alexis C., Oct 29 '15 at 00:23
Oh so it's not a compilation error but a runtime error. Well, `head` is `null` when you exit your `while` loop; and you try to access its `data` field. — Alexis C., Oct 29 '15 at 00:25

eugenioy · Accepted Answer · 2015-10-29T00:36:35.100

3

You need to create a new node at the end as well.

Also, don't wait until "head==null" or you'll reach the end of the list and you won't know where to insert the node.

You need to go until "head.next==null" so that you end up at the current last node.

Also, if you must always return the Head of the list, you should copy the reference before starting the iteration, as noted in the comments.

Node Insert(Node head,int data) {
    if(head == null) {
       Node node = new Node();
       head = node;
       head.data = data;
       head.next = null;
       return head;
    }

    Node current = head;

    while(current.next != null) {
        current = current.next;
    }

    Node node = new Node();
    node.data = data;
    node.next = null;

    current.next = node;

    return head;
}

edited Oct 29 '15 at 00:36

answered Oct 29 '15 at 00:25

eugenioy

11,825
28
35

You should first copy the head reference and use that copy to iterate through the list. If you use head, then you'll lose access to the head of the list, and you'll always be returning the last inserted node. – turingcomplete Oct 29 '15 at 00:31
@turingcomplete yeah. The requirement is we must return the head of the node. – theGreenCabbage Oct 29 '15 at 00:32
@theGreenCabbage: you say the method must always return the head node? I'll edit the code to do so... – eugenioy Oct 29 '15 at 00:33
@eugenioy yes, you must return the head node – theGreenCabbage Oct 29 '15 at 00:34
@theGreenCabbage: done, check out the new code – eugenioy Oct 29 '15 at 00:37
Thank you @eugenioy. Can you explain why we need to create a new node for each of these iterations? That was the part that confused me. – theGreenCabbage Oct 29 '15 at 00:38
@theGreenCabbage: well, if you need to insert new data, you need to create a new Node to host that data. In other words, how would you be adding new nodes to the list without creating new Node objects? – eugenioy Oct 29 '15 at 00:39

Appending a node to end of tail with Java

1 Answers1