如何通过JavaScript在链表中插入元素

Question

我从LeetCode得到了这个问题

问题21，https://leetcode.com/problems/merge-two-sorted-lists/
但这不仅仅是为了解决这个问题

这是我对我的问题的描述我有一个原始的链表[1，2，4]，它的数据结构是这样的：

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

我想在2之后插入3，并使其成为[1，2，4]
几乎从我读过的所有教程中，他们都告诉我要这样做：

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

但是p是[2,3,4]，因为当完成while循环时，p已经被赋值为[2,4]，显然这是不对的
那么我该如何解决这个问题
以及为什么教程会说类似于
find the node(p) you want to insert after,and create a new node(q), and q.next = p.next ;p.next = q？

Answer 1

您不应该返回p，而是返回lst。

当然，我建议不要在函数中对值和循环条件进行硬编码，而是将它们作为参数传递给函数。

此外，当您想调用insert在列表的最开始插入值时，您需要一段单独的代码：

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

Answer 2

请尝试这个

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