Creating a singly linked list out of an array of integers

Question

I'm having trouble with taking an array of integers and creating a singly linked list with JavaScript. It sounds easy enough, but there's something I'm just not seeing with the function I have an I'd appreciate any help you can provide.

This is the constructor function I use to make nodes:

 function ListNode(val) {
     this.val = val;
     this.next = null;
 }

And this is the function I'm writing that is supposed to take an array and create a linked list out of it. The basic idea is just a while loop that shifts off the first value until there's nothing left to shift:

var createLinkedList = function(array) {
    var head = new ListNode(parseInt(array[0]));
    array.shift();
    while(array.length) {
        var prev = new ListNode(parseInt(array[0]));
        head.next = head;
        prev = head;
        array.shift();
    }
    return head;
}

I've tried running this with a couple basic arrays and it always just returns the last value in the array instead of a linked list. Is there something simple I'm just not seeing here? Thanks in advance.

Hint: `head.next = head` creates a circular reference. And what do you think `prev = head` does? — nnnnnn, Dec 05 '17 at 02:25
As an aside, note that you can say `parseInt(array.shift())` to get the value of the first element and remove it all in one line, you don't need to use `array[0]` and `array.shift()` separately. — nnnnnn, Dec 05 '17 at 02:26

score 1 · Answer 1 · answered Dec 05 '17 at 02:34

1

The problem is not with array.shift, but how you link the nodes together inside the while loop.

To chain the nodes together, essentially you need to do:

var new_node = new ListNode(parseInt(array[0]));
head.next = new_node;
new_node = new ListNode(parseInt(array[1]));
head.next.next = new_node;
new_node = new ListNode(parseInt(array[2]));
head.next.next.next = new_node;
.
.
.

I think you get the idea. So what you want to do is rework your while loop, store a reference of the tailNode so instead of calling head.next.next.next.next.next = newNode, you can call tailNode.next = newNode, and tailNode = newNode inside the while loop.

answered Dec 05 '17 at 02:34

mckuok

744
6
11

I'm trying that but I don't know how to link the head to the beginning. [link]https://jsfiddle.net/9xh5b5kr/ is what I have now, but I don't get how to link to the head if that makes sense. – amacdonald Dec 05 '17 at 02:54
You have `current.next = current;` which creates a circular reference and not meaningful in a singly linked list. Try see this [link](https://jsfiddle.net/9xh5b5kr/) and think about the relationship between the newNode, and the tail node. – mckuok Dec 05 '17 at 03:01
I'm really lost here. https://jsfiddle.net/9xh5b5kr/ is what I tried so far, and it just creates a head and a tail using the first and last values of the array and ignores everything in between. – amacdonald Dec 05 '17 at 03:18
Sorry, I forgot to fork the link, here is the new link https://jsfiddle.net/Lyxbsf6b/ . Feel free to tag me if you are confused with the structure. – mckuok Dec 05 '17 at 03:22
Ah, yeah, I see it now. I was confused why the previous linkw as just my old link. Quick question though, how come you don't have to declare tail as a var? – amacdonald Dec 05 '17 at 03:40
See [this] (https://stackoverflow.com/questions/2485423/is-using-var-to-declare-variables-optional) for difference between no `var` and with `var`. I forgot to put the `var` keyword and I got very lucky that there is no `tail` variable declared in the global scope. Bad example! – mckuok Dec 05 '17 at 03:45
I just realized I forgot to say thank you. This was all very helpful, so thanks again! – amacdonald Dec 06 '17 at 18:21

Creating a singly linked list out of an array of integers

1 Answers1