how to insert an element in linked list by JavaScript

Question

I got this problem from LeetCode

question 21,https://leetcode.com/problems/merge-two-sorted-lists/
but it's not only to solve this question

here is my description of my problem I have a original linked list [1,2,4],it's data structure is like :

  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
  }

I want to insert 3 after 2, and make it to [1,2,3,4].
almost from all the tutorials I've read ,they tell me to do like this:

var insert = function(l1) {
    let i=0;
    let p = l1;
    while(i<1 && p){
        p = p.next;
        i++;
    }
    let tem = new ListNode(3,p.next);
    p.next = tem;
    return p;
};

but the p is [2,3,4] because p is already assign to be [2,4] when finish the while loop ,obviously this is not right .
so how can I fix this?
and why the tutorials say like
find the node(p) you want to insert after,and create a new node(q), and q.next = p.next ;p.next = q?

What of the proposed "algorithm" is it that you don't understand? — Andreas
– Andreas, Commented Oct 3, 2020 at 16:12
Why do you stop your while loop after the first iteration? You're not even testing at which node in the list you're currently. — Andreas
– Andreas, Commented Oct 3, 2020 at 16:13
@Andreas sorry for not say it clearly ,I was doing this in a testing purpose ,for getting node 2 in a straight way ,I hard-code it. — Jim
– Jim, Commented Oct 3, 2020 at 16:50
Try and implement this and see far you get. Post the code here as a snippet if you're still having problems. That will make it far easier for people to assist you. — Richard Hunter
– Richard Hunter, Commented Oct 3, 2020 at 21:38

trincot · Accepted Answer · 2020-10-03 16:19:46Z

1

You should not return p, but lst.

I would of course suggest to not hard-code the value and the loop condition inside your function, but to pass those as arguments to your function.

Also, you would need a separate piece of code for when you want to call insert for inserting a value at the very start of the list:

function ListNode(val=0, next=null) { // use defaults
    this.val = val;
    this.next = next;
}

var insert = function(l1, index, value) {
    if (index == 0) return new ListNode(value, l1);
    let i = 1; // start at 1
    let p = l1;
    while(i<index && p){
        p = p.next;
        i++;
    }
    let tem = new ListNode(value, p.next);
    p.next = tem;
    return lst; // return the list
};

function toArray(lst) { // utility to help display the list
    return lst ? [lst.val].concat(toArray(lst.next)) : [];
}

let lst = new ListNode(1, new ListNode(2, new ListNode(4)));

lst = insert(lst, 2, 3); // insert value 3 at index 2 

console.log(toArray(lst));

answered Oct 3, 2020 at 16:19

trincot

357k38 gold badges282 silver badges338 bronze badges

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

1 Comment

Jim Over a year ago

this is exactly what I was misunderstanding ,thanks a lot ,got it

elkabelaya · Accepted Answer · 2020-10-03 17:04:51Z

please, try this one

class LinkedList{
    constructor(val){
        this.head = new ListNode(val);
        this.tail = this.head;
    }
    
    add(val){
        this.tail.next = new ListNode(val);
        this.tail = this.tail.next;
    }
    
    insert(val, after){
        let node = this;
      
        while(node){
                        //find the node you want to insert after
            if ( node.val === after){
                                //and create a new node,  and q.next = p.next ;p.next = q
                node.next = new ListNode(val, node.next);
                                //break
                node = null;
            } else {
                            //node is not fouund still
              node = node.next;
            }
            
        }
    }
}


class ListNode{
   constructor(val, next) {
      this.val = (val===undefined ? 0 : val);
      this.next = (next===undefined ? null : next);
   }
  }
  
  
  var list = new LinkedList(1);//1
  list.add(2);//1->2
  list.add(4);//1->2->4
  list.insert(3,2);//1->2->3->4

Collectives™ on Stack Overflow

how to insert an element in linked list by JavaScript

I got this problem from LeetCode

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

I got this problem from LeetCode

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related