Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Published
20 hours ago •
Advanced-Frontend
Advanced-Frontend
第 115 题：写一个单向链数据结构的 js 实现并标注复杂度
class LinkList {
constructor() {
this.head = null
}
find(value) {
let curNode = this.head
while (curNode.value !== value) {
curNode = curNode.next
}
return curNode
}
findPrev(value) {
let curNode = this.head
while (curNode.next!==null && curNode.next.value !== value) {
curNode = curNode.next
}
return curNode
}
insert(newValue, value) {
const newNode = new Node(newValue)
const curNode = this.find(value)
newNode.next = curNode.next
curNode.next = newNode
}
delete(value) {
const preNode = this.findPrev(value)
const curNode = preNode.next
preNode.next = preNode.next.next
return curNode
}
}
class Node {
constructor(value, next) {
this.value = value
this.next = null
}
}
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
#firstNode;
constructor() {
this.#firstNode = null;
}
get firstNode() {
return this.#firstNode;
}
insertAfter(node, newNode) {
if (!newNode) return;
if (node) {
newNode.next = node.next;
node.next = newNode;
}
else {
newNode.next = this.#firstNode;
this.#firstNode = newNode;
}
}
insertBeginning(newNode) {
this.insertAfter(null, newNode);
}
removeAfter(node) {
if (node) {
node.next = node.next.next;
}
else if (this.#firstNode) {
this.#firstNode = this.#firstNode.next;
}
}
removeBeginning() {
this.removeAfter(null);
}
}
var list = new SinglyLinkedList();
list.insertBeginning(new Node("a"));
list.insertAfter(list.firstNode, new Node("d"));
list.insertAfter(list.firstNode, new Node("c"));
list.insertAfter(list.firstNode, new Node("b"));
var currentNode = list.firstNode;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
list.removeBeginning(); // Remove 'a'
list.removeAfter(list.firstNode); // Remove 'c' after 'b'
var currentNode = list.firstNode;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
class ListNode {
constructor(val) {
this.val = val
this.next = null
}
}
class LinkedList {
head = null
tail = null
size = 0
// 时间复杂度O(n)
get = index => {
if (index < 0) return -1
let node = this.head
for (let i = 0; i < index; i++) {
if (!node) return -1
node = node.next
}
return node ? node.val : -1
}
// 时间复杂度O(1)
addAtHead = val => {
const node = new ListNode(val)
if (!this.head) {
this.head = this.tail = node
} else {
node.next = this.head
this.head = node
}
this.size++
}
// 时间复杂度O(1)
addAtTail = val => {
const node = new ListNode(val)
if (!this.tail) {
this.head = this.tail = node
} else {
this.tail.next = node
this.tail = node
}
this.size++
}
// 时间复杂度O(n)
addAtIndex = (index, val) => {
const node = new ListNode(val)
if (index > this.size) return
if (index === this.size) return this.addAtTail(val)
if (index <= 0) return this.addAtHead(val)
let head = this.head
for (let i = 1; i < index; i++) {
if (!head) return
head = head.next
}
node.next = head.next
head.next = node
this.size++
}
// 时间复杂度O(n)
deleteAtIndex = index => {
let head = this.head
if (!head || index >= this.size || index < 0) return
if (index === 0) {
if (this.size === 1) {
this.head = this.tail = null
} else {
this.head = this.head.next
}
this.size--
return
}
for (let i = 1; i < index; i++) {
if (!head) return
head = head.next
}
if (!head) return
if (head.next) {
if (head.next === this.tail) {
this.tail = head
head.next = null
} else {
head.next = head.next.next
}
} else {
this.head = this.tail = null
}
this.size--
}
}
class Node {
constructor(value,next) {
this.value = value;
this.next = next;
}
}
class LinkList {
constructor(value) {
this.head = new Node(value);
}
add(newVal, val) {
const newNode = new Node(newVal);
const curNode = this.find(val);
newNode.next = curNode.next;
curNode.next = newNode;
return newNode;
}
// 时间复杂度O(n)
find(value){
let curNode = this.head;
while(curNode.value != value && curNode) {
curNode = curNode.next ? curNode.next : null;
}
return curNode;
}
del(val) {
let prevNode = this.findPrev(val);
let curNode = prevNode.next;
prevNode.next = curNode.next;
return curNode;
}
findPrev(val) {
let curNode = this.head;
while(curNode && curNode.next && curNode.next.value !== val ) {
curNode = curNode.next ? curNode.next : null;
}
return curNode;
}
print() {
let curNode = this.head;
while(curNode){
console.log(curNode.value);
curNode = curNode.next;
}
}
}
const link = new LinkList('11');
link.add('22','11');
link.add('33','22');
link.del('22');
link.print();
class Node { constructor(value,next) { this.value = value; this.next = next; } } class LinkList { constructor(value) { this.head = new Node(value); } add(newVal, val) { const newNode = new Node(newVal); const curNode = this.find(val); newNode.next = curNode.next; curNode.next = newNode; return newNode; } // 时间复杂度O(n) find(value){ let curNode = this.head; while(curNode.value != value && curNode) { curNode = curNode.next ? curNode.next : null; } return curNode; } del(val) { let prevNode = this.findPrev(val); let curNode = prevNode.next; prevNode.next = curNode.next; return curNode; } findPrev(val) { let curNode = this.head; while(curNode && curNode.next && curNode.next.value !== val ) { curNode = curNode.next ? curNode.next : null; } return curNode; } print() { let curNode = this.head; while(curNode){ console.log(curNode.value); curNode = curNode.next; } } } const link = new LinkList('11'); link.add('22','11'); link.add('33','22'); link.del('21'); link.print();
我删除node的时候假如把head传进去，这个方法就不对了
//链表节点 class Node { constructor(element) { this.element = element this.next = null } }
//链表 class LinkedList { constructor() { this.head = null this.length = 0 }
//追加元素
append(element) {
const node = new Node(element)
let current = null
if (this.head === null) {
this.head = node
} else {
current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.length++
}
//任意位置插元素
insert(position, element) {
if (position >= 0 && position <= this.length) {
const node = new Node(element)
let current = this.head
let previous = null
let index = 0
if (position === 0) {
this.head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
this.length++
return true
}
return false
}
//移除指定位置元素
removeAt(position) {
//检查越界
if (position > -1 && position < length) {
let current = this.head
let previous = null
let index = 0
if(position === 0){
this.head = current.next
}else{
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
return null
}
//寻找元素下标
findIndex(element){
let current = this.head
let index = -1
while(current){
if (element === current.element){
return index + 1
}
index++
current = current.next
}
return -1
}
//删除指定文档
remove(element){
const index = this.indexOf(element)
return this.removeAt(index)
}
isEmpty(){
return !this.length
}
size(){
return this.length
}
//转为字符串
toString(){
let current = this.head
let string = ''
while(current){
string += '$(current.element)'
current = current.next
}
return string
}
}
正好学习的时候照着写过，不过时间复杂度和空间复杂度我都不太懂💔
神仙题，，，看不懂咋办
那就多学呗，https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/156#issuecomment-512079990
class Node { constructor(value, next) { this.value = value; this.next = next; } }
class LinkList { constructor(value) { const node = new Node(value, null); this.linkList = node; this.currentNode = node; }
_delete(value, node, preNode) {
const currentValue = node.value;
const nextNode = node.next;
if (currentValue === value) {
if (nextNode) {
preNode.next = nextNode;
} else {
preNode.next = null;
}
} else {
if (node.next) {
this._delete(value, node.next, node);
}
}
}
insert(value) {
// o(1)
const nextNode = new Node(value, null);
this.currentNode.next = nextNode;
this.currentNode = nextNode;
return this;
}
delete(value) {
// O(n)
if (this.linkList.next) {
if (this.linkList.value === value) {
this.linkList = this.linkList.next;
} else {
this._delete(value, this.linkList.next, this.linkList);
}
} else {
if (value === this.linkList.value) {
this.linkList = new Node(null, null);
}
}
return this;
}
_findNode(value, node) {
if (node.value == value) {
return node;
} else {
const nextNode = node.next;
if (nextNode) {
return this._findNode(value, nextNode);
}
return null;
}
}
findNode(value) {
return this._findNode(value, this.linkList);
}
getNode() {
return this.linkList;
}
}
常规的解法就是增删改查，修改next的指向和value值或者删除增加节点。这里不再走寻常路。维护一个数组，通过代理数组操作返回链表。数组<item, index, array>型的api基本都是O(n)时间复杂度和O(1)空间复杂度，但是这里最后会有一个全部遍历同步的操作，额外稳定增加O(n)时间复杂度。如果想做到O(1)复杂度的修改，则需要劫持每一个数组操作，并利用额外缓存存下各种信息，大约还需要O(n)空间复杂度才能换取O(1)的时间复杂度
class LinkList {
constructor(...args) {
this.temp = []
this.temp.push(...args)
}
}
function createLinkList(...init) {
const ret = new LinkList(...init)
let current
const result = ret.temp.reduce((res, cur) => {
current = current || res
current.value = cur
current.next = current.next || {}
current = current.next
return res
}, Object.create(new Proxy(ret.temp, {
get(target, name) {
const record = Reflect.get(target, name)
if (typeof record === 'function') {
return (...args) => {
const retVal = Reflect.apply(record, target, args)
let current = result
ret.temp.forEach(item => {
current.value = item
current = current.next || {}
})
return retVal
}
}
return record
}
})))
return result
}
const mockLinkList = createLinkList(1,2,3)
mockLinkList.push(1, 2)
mockLinkList.pop()
// ......所有的数组操作
const head = Symbol('head');
class LinkListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkList {
constructor() {
this[head] = null;
}
add(data) {
const newNode = new LinkListNode(data);
if (this[head] === null) {
this[head] = newNode;
} else {
let current = this[head];
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
insertBefore(data, index) {
const newNode = new LinkListNode(data);
if (this[head] === null) {
throw new RangeError(`index ${index} does not exist in this list`);
}
if (index == 0) {
newNode.next = this[head];
this[head] = newNode;
} else {
let current = this[head],
previous = null;
let i = 0;
while (current.next !== null && i < index) {
previous = current;
current = current.next;
i++;
}
if (i < index) {
throw new RangeError(`index ${index} does not exist in the list`);
}
previous.next = newNode;
newNode.next = current;
}
}
insertAfter(data, index) {
const newNode = new LinkListNode(data);
if (this[head] === null) {
throw new RangeError(`index ${index} does not exist in the list`);
}
let current = this[head];
let i = 0;
while (current != null && i < index) {
current = current.next;
i++;
}
if (i < index) {
throw new RangeError(`index ${index} does not exist in the list`);
}
newNode.next = current.next;
current.next = newNode;
}
get(index) {
if (index > -1) {
let current = this[head];
let i = 0;
while (current != null && i < index) {
current.next = currnt;
i++;
}
return current !== null ? current.data : undefined;
} else {
return undefined;
}
}
indexOf(data) {
let current = this[head];
let index = 0;
while (current !== null) {
if (current.data === data) {
return index;
}
current = current.next;
index++;
}
return -1;;
}
remove(index) {
if (this[head] === null || index < 0) {
throw new RangeError(`index ${index} does not exist in the list`);
}
if (index === 0) {
const data = this[head].data;
this[head] = this[head].next;
return data;
}
let currnet = this[head];
let previous = null;
let i = 0;
while (currnet !== null && i < index) {
previous = currnet;
currnet = currnet.next;
i++;
}
if (currnet !== null) {
previous.next = currnet.next;
return currnet.data;
}
throw new RangeError(`index ${index} does not exist in the list`);
}
clear() {
this[head] = null;
}
get size() {
if (this[head] === null) {
return 0;
}
let current = this[head];
let count = 0;
while (current != null) {
current = current.next;
count++;
}
return count;
}
/**
* The default iterator for the class.
* @returns {Iterator} An iterator for the class.
*/
[Symbol.iterator]() {
return this.values();
}
/**
* Create an iterator that returns each node in the list.
* @returns {Iterator} An iterator on the list.
*/
*values() {
let current = this[head];
while (current !== null) {
yield current.data;
currnet = current.next;
}
}
/**
* Converts the list into a string representation.
* @returns {String} A string representation of the list.
*/
toString() {
return [...this].toString();
}
}
/**
单向链表
链表：由多个节点构成，每个节点包含自身数据和指向下个节点的引用
物理上可以不连续但逻辑上必须连续（不一定是一块连续的内存）
链表是一种常见的基础数据结构，是一种线性表，但是不会按线性的顺序存储数据而是每个节点存指向下个节点的引用
*/
class LinkNode {
constructor(val) {
if (val === void 0) throw new Error('请输入链表节点值')
this.node = val
this.next = null
}
}
class LinkList {
head = null
size = 0
// 有没有初始化的方法呢 ？？？
initLinkedList() {}
/**
* @description: 根据索引获取 node，从头部遍历
* @param {index}
* @return: linkNode
*/
findNode(index) {
if (index < 0 || index >= this.size || this.size == 0) return null
let node = this.head
for (let i=0; i<index; i++) {
if (!node) return null
node = node.next
}
return node ? node : null
}
// 时间复杂度 O(n)
get(index) {
return this.findNode(index)
}
// 时间复杂度 O(n)
push(val) {
const node = new LinkNode(val)
if (!this.head) {
this.head = node
} else {
let tail = this.findNode(this.size - 1)
tail.next = node
}
this.size++
return this
}
// 时间复杂度 O(1)
unshift(val) {
const node = new LinkNode(val)
if (!this.head) {
this.head = node
} else {
let temp = this.head
this.head = node
this.head.next = temp
}
this.size++
return this
}
// 时间复杂度 O(1)
shift() {
if (!this.head) return -1
this.head = this.head.next
this.size--
return this
}
// 时间复杂度 O(2n)
pop() {
return this.removeAtIndex(this.size-1)
}
// 时间复杂度 O(2n)
removeAtIndex(index) {
if (!this.head || index >= this.size || index < 0 || this.size == 0) return
const prevNode = this.findNode(index-1)
const nextNode = this.findNode(index+1)
const currNode = this.findNode(index)
// 正常情况
if (prevNode && nextNode) {
prevNode.next = nextNode
}
// 索引为 0, size 大于 1 === shift
if (!prevNode && nextNode) {
this.head = this.head.next
}
// 索引为 size-1 === pop
if (prevNode && !nextNode) {
prevNode.next = null
}
// 索引为 0，size为 1
if (!prevNode && !nextNode) {
this.head = null
}
this.size--
return currNode
}
// 时间复杂度 O(2n)
addAtIndex(val, index=this.size) {
const node = new LinkNode(val)
if (!node && (index > this.size || index < 0)) return
// 尾不追加
if (this.size === 0 || index === this.size) return this.push(node)
// 头部追加
if (index === 0) return this.unshift(node)
// 中间部位
const prevNode = this.findNode(index-1)
const nextNode = this.findNode(index+1)
prevNode.next = node
node.next = nextNode
this.size++
return this
}
// 清空单链表
clear() {
this.head = null
this.size = 0
return this
}
// 翻转链表
reverse() {
if (this.head === null || this.head.next === null) return this.head
// ... 待更新
return this
}
}
var list = new LinkList()
list.push('a').push('b').push('c')
console.log(list)
// 单向
class Node{ constructor(val){ this.val = val; this.next = null; } }
class oneWayList{
constructor(){
this.first = null;
this.last = null;
this.size = 0;
}
addFirst = val => {
let node = new Node(val);
if(this.size==0) {
this.first = this.last = node;
} else {
node.next = this.first;
this.first = node;
}
this.size++;
}
addLast = val => {
let node = new Node(val);
if(this.size ==0 ) {
this.first = this.last = node;
} else{
this.last.next = node;
this.last = node;
}
this.size++;
}
add = (index, val ) =>{
let node = new Node(val);
let point = this.first;
if(index ==0 ) return this.addFirst(val);
if( index == this.size ) return this.addLast(val);
if(index<0 || index>this.size) return;
for(let i=1; i<index; i++) {
point = point.next;
}
node.next = point.next;
point.next = node;
this.size++;
}
deleteFirst = () =>{
if(this.size===0) return;
if(this.size ===1) this.first = this.last = null;
let first = this.first;
this.first = this.first.next;
first.next = null;
this.size--;
};
deleteLast = () =>{
let point = this.first;
if(this.size===0) return;
if(this.size ===1) this.first = this.last = null;
for(var i =1; i<this.size-1;i++){
point = point.next;
}
point.next = null;
this.last = point;
this.size--;
}
delete = index =>{
let point = this.first;
let deleteNode;
if(this.size===0) return ;
if(index === 0 ) return this.deleteFirst();
if(index === this.size-1 ) return this.deleteLast();
for(var i=1; i<index-1; i++ ) {
point = point.next;
}
deleteNode = point.next;
point.next = point.next.next;
deleteNode.next = null;
this.size--;
}
set = (index,val,type) =>{
let point = this.first;
if(this.size===0 || index<0 || index>this.size-1) return;
for(var i=1; i<index; i++ ) {
point = point.next;
}
if(type==='get') {
return point.val;
} else {
point.val = val;
}
}
get = index =>{
return this.set(index,'','get');
}
}
////////////////////////////////////////////////////////////////////////////// // 双向 class Node{ constructor(val){ this.val = val; this.prev=null; this.next=null; } }
class twoWayList{
constructor(){
this.first=null;
this.last = null;
this.size =0;
}
addFirst = val =>{
let node = new Node(val);
if(this.size===0) {
this.first = this.last = node;
} else {
node.next = this.first;
this.fist.prev=node;
this.first = node;
}
this.size++;
}
addLast = val => {
let node = new Node(val);
if(this.size===0) {
this.first = this.last = node;
} else {
node.prev = this.last;
this.last.next=node;
this.last = node;
}
this.size++;
}
add=(index,val) =>{
let node = new Node(val);
let point = this.first;
if(index===0) return this.addFirst(val);
if(index===this.size) return thsi.addLast(val);
if(index<0 || index>this.size) return;
for(var i=1;i<index;i++) {
point = point.next;
}
node.prev= point;
node.next = point.next;
point.next.prev = node;
point.next = node;
this.size++;
}
deleteFirst = ()=>{
if(this.size===0) return;
if(this.sieze===1) {
this.first = this.last = null;
} else {
this.first = this.first.next;
this.first.prev.next = null;
this.first.prev = null;
}
this.sieze--;
}
deleteLast = () => {
if(this.size===0) return;
if(this.size===1) {
this.first = this.last = null;
} else {
this.last = this.last.prev;
this.last.next.prev = null;
this.last.next = null;
}
this.sieze--;
}
delete = index => {
let point = this.first;
if(index===1) return this.deleteFirst();
if(index === this.size) return this.deleteLast();
if(index<=0 || index>this.size ) return;
for(let i=1;i<index;i++) {
point = point.next;
}
point.prev.next = point.next;
point.next.prev = point.prev;
point.prev = point.next = null;
this.size--;
}
set = (index,val) => {
let point = this.first;
if(index<=0 || index>this.size) return;
if(index===1) {
return point.val=val;
}
for(var i=1;i<index;i++) {
point= point.next;
}
point.val = val;
}
get = (index) =>{
let point = this.first;
if(index<=0 || index>this.size) return;
if(index===1) {
return point.val;
}
for(var i=1;i<index;i++) {
point= point.next;
}
return point.val;
}
}
复杂度O(n)
class Node{
constructor(data){
this.data=data
this.next=null
}
}
class LinkedList{
constructor(){
this.head=null
this.tail=null
}
push(data){
const node=new Node(data)
if(!this.head){
this.head=node
this.tail=node
}
this.tail.next=node
this.tail=node
}
...
}
参考这篇文章：https://mp.weixin.qq.com/s/my_lAFqYGTrr8smxNSlUqg
class Node {
constructor(val){
this.val = val;
this.next = null
}
}
class NodeList{
constructor(array){
array.forEach((val,index)=>{
index == 0?this.head = new Node(val) : this.insertNewNode(val)
})
}
insertNewNode(val){
let cur = this.head ;
while(cur.next){
cur = cur.next
}
cur.next = new Node(val)
}
/**
* ohter methods
* ...
* ...
* ..
* */
}
class LinkList { constructor() { this.head = null } find(value) { let curNode = this.head while (curNode.value !== value) { curNode = curNode.next } return curNode } findPrev(value) { let curNode = this.head while (curNode.next!==null && curNode.next.value !== value) { curNode = curNode.next } return curNode } insert(newValue, value) { const newNode = new Node(newValue) const curNode = this.find(value) newNode.next = curNode.next curNode.next = newNode } delete(value) { const preNode = this.findPrev(value) const curNode = preNode.next preNode.next = preNode.next.next return curNode } } class Node { constructor(value, next) { this.value = value this.next = null } }
find 中，curnode.next =null 时，null.value 是会报错的---》
链表没有随机访问的能力，获取第n个元素需要从第一个元素逐步查询 增删改查的时间复杂度是o(n)
const LinkList = (function () {
class _Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkList {
constructor() {
this.head = null;
}
find(val) {
let node = this.head;
while (node && node.value !== val) {
node = node.next;
}
return node;
}
findPre(val) {
let node = this.head;
while (node) {
if (node.next && node.next.value === val) {
break;
}
node = node.next;
}
return node;
}
delete(val) {
let preNode = this.findPre(val);
let curNode;
if (preNode) {
curNode = preNode.next;
preNode.next = curNode.next;
}
else {
curNode = this.find(val);
if (curNode) {
this.head = curNode.next;
}
}
return curNode;
}
unshift(val) {
let node = new _Node(val);
let first = this.head;
if (!first)
this.head = node;
else {
node.next = first;
this.head = node;
}
return node;
}
push(val) {
let node = new _Node(val);
let curNode = this.head;
while (curNode && curNode.next) {
curNode = curNode.next;
}
!curNode ? this.head = node : curNode.next = node;
return node;
}
insert(newValue, value) {
let newNode = new _Node(newValue);
let curNode = this.find(value);
if (!curNode)
this.unshift(newValue);
else {
newNode.next = curNode.next;
curNode.next = newNode;
}
return newNode;
}
}
return LinkList;
}());
// 单向链表
class ListNode{
constructor(val, next=null){
this.val = val
this.next = next
}
}
class List {
#head = null;
#size = 0;
// 末尾追加节点
appendNode(newNode){
if(this.isEmpty()){
this.#head = newNode
} else {
let tail = this.#head;
while(tail.next){
tail = tail.next
}
tail.next = newNode
}
this.#size ++
}
// 指定节点前面插入节点
insertBefore(newNode, referenceNode){
if(!referenceNode) return false
if(this.isEmpty()) return false
// 插入头节点前面
if(referenceNode === this.#head){
newNode.next = this.#head
this.#head = newNode
this.#size ++
return
}
// 插入其他节点前面
let prev = this._findPrevNode(referenceNode)
if(!prev) return false
prev.next = newNode
newNode.next = referenceNode
this.#size ++
return true
}
// 删除指定节点
removeNode(node){
if(!node) return false
if(this.isEmpty()) return false
// 删除头节点
if(node === this.#head){
this.#head = node.next;
node.next = null
this.#size --
return true
}
// 删除其他节点
let prev = this._findPrevNode(node)
if(!prev) return false
prev.next = node.next
node.next = null
this.#size --
return true
}
// 按值查找节点
findNodeByVal(val){
let node = this.#head
while(node){
if(node.val === val){
return node
}
node = node.next
}
return null
}
// 查找节点前面的邻居
_findPrevNode(node){
if(this.isEmpty()) return null
let prev = this.#head;
while(prev.next!==node){
prev = prev.next;
}
if(prev.next === node){
return prev
}
return null
}
// 是否为空
isEmpty(){
return this.#head === null
}
// 获取链表长度
size(){
return this.#size
}
}
