[数据结构与算法]前端Javascript算法题（三）

1、链表

介绍：多个元素组成的列表，元素之间的存储不连续，用next指针连在一起。

2、数组 VS 链表

增删非首尾元素，不需要移动元素，只需要更改next指针即可。

3、Js中的链表

js中没有链表，但可以使用Object来模拟链表。

const a = { val:'a' };
const b = { val:'b' };
const c = { val:'c' };
const d = { val:'d' };

a.next = b;
b.next = c;
c.next = d;

//遍历列表操作
let p = a;
while(p){
    console.log(p.val);
    p = p.next;
}

//插入操作
const e = { val:'e'}
c.next = e;
e.next = d;

//删除操作
c.next = d; 

题目：

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 --?head =?[4,5,1,9]，它可以表示为: 4 -> 5 -> 1--> 9

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为?5?的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

解题思路：

无法直接获取被删除节点的上一个节点，将被删除的节点转移到下个节点。删除下一节点即可。

var deleteNode = function(node){
    node.val = node.next.val;
    node.next = node.next.next;
}