CODEWITHSUNDEEP
javascriptalgorithmecmascript-6linked-list
Jim
Jim

Reputation: 11

how to insert an element in linked list by JavaScript

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?

Upvotes: 0

Views: 3629

Answers (2)

elkabelaya
elkabelaya

Reputation: 26

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

Upvotes: 0

trincot
trincot

Reputation: 350310

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));

Upvotes: 1

Related Questions