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
– nnnnnn, Commented Dec 5, 2017 at 2: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
– nnnnnn, Commented Dec 5, 2017 at 2:26

mckuok · Accepted Answer · 2017-12-05 02:34:49Z

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 5, 2017 at 2:34

mckuok

7546 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

amacdonald Over a year ago

I'm trying that but I don't know how to link the head to the beginning. [link]jsfiddle.net/9xh5b5kr is what I have now, but I don't get how to link to the head if that makes sense.

mckuok Over a year ago

You have current.next = current; which creates a circular reference and not meaningful in a singly linked list. Try see this link and think about the relationship between the newNode, and the tail node.

amacdonald Over a year ago

I'm really lost here. 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.

mckuok Over a year ago

Sorry, I forgot to fork the link, here is the new link jsfiddle.net/Lyxbsf6b . Feel free to tag me if you are confused with the structure.

amacdonald Over a year ago

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?

|

Collectives™ on Stack Overflow

Creating a singly linked list out of an array of integers

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related