【校招VIP】2022秋招-前端学习记录-算法/链表入门- 校招VIP

转载声明：文章来源https://blog.csdn.net/weixin_41831917/article/details/118857224

1、从斐波那契数列入门

2、js怎么实现链表：
单向链表代码实现：

3、以上简单了解链表，继续牛客网算法题
JZ3：链表的反向输出
JZ16: 合并两个排序的链表

1、从斐波那契数列入门

斐波那契数列如下：
0 1 2 3 4 5 6 7…
0 1 1 2 3 5 8 13…

使用JavaScript编程，想法是用数组把整个数列存起来，
第n个数由 arr[n-2]+arr[n-1]得出
代码如下：

function Fibonacci(n){
    // write code here
    var sum = [0,1];
    for(var i = 2; i<=n; i++){
    	// sum.push(sum[i-2]+sum[i-1]); 效果一样
    	sum[i] = sum[i-2]+sum[i-1];
    }
    return sum[n];
}

通过了，运行时间有点长，因为用了数组存整条斐波那契数列。

第一名（JavaScript）的代码：

function Fibonacci(n){
   if(n==0||n==1)
       return n;
  let a =0,b=1,c;
  for(let i = 2;i<n+1;i++){
      c = a+b;
      a=b;
      b=c;
  }
  return c;
}

不用数组，占内存小。

2、js怎么实现链表：

b站视频：https://www.bilibili.com/video/BV1P5411H77a?from=search&seid=8097380973513222466

视频学习笔记：
有序数据类型：数组，有序的线性结构，在内存开辟了连续的空间来存储数组的数据；
而链表可以指向不连续的内存空间。

1、单向链表：
单向链表是有序的线性数据结构。

利用Next指针连续指向下一个节点。

2、双向链表：

3、单向循环链表（一个闭环）

4、双向循环链表（两个闭环）：

5、环形链表：

前端的面试基本只问第一个单向链表；其他大概率是不问的

单向链表代码实现：

class Node{
	constructor(ele){
		this.ele= ele;
		this.next = null;
	}
}

class LinkedList{
	constructor(){
		this.size = 0;
		this.head = null;
	}
	
	// 添加元素方法，与数组的push方法类似
	funPush(ele){
		let node = new Node(ele);
		if(this.head === null){
			this.head = node;
		}else{
			let nodePre = this.getNode(this.size - 1);
			nodePre.next = node;
		}
		this.size++;
	}	
	// 这个方法用来，输入索引index，就获取索引对应的那个Node对象
	getNode(index){
		if(index<0 || index>=this.size){
			throw new Error('error!')
		}
		let current = this.head;
		for(let i =0; i<index; i++){
			current = current.next;
		}
		return current;	
	}	
}

let linked = new LinkedList();
linked.funPush(1);
linked.funPush(2);
linked.funPush(3);
console.log(linked);

以上简单实现了添加元素的功能。
输出结果如下：

3、以上简单了解链表，继续牛客网算法题

JZ3：链表的反向输出

因为输出为一个数组，所以需要一开始定义一个空数组来存。然后遍历链表，用for循环不太可行，不知道链表里有没有存size。末尾节点指向空，即null，所以用while来遍历，遍历node的next

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    // write code here
    let arr = [];
    let node = head;
    while(node){
		arr.push(node.val);
		node = node.next;
	}
	return arr.reverse();
}

补充数组知识点：数组的 reverse 方法， arr.reversr(); 作用是颠倒数组内的所有元素，没有参数、会改变自身(arr)、返回被改变颠倒的arr本身（数组）。

MDN链接：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/reverse

JZ16: 合并两个排序的链表

1、这里需要定义一个空链表alist 来保存排序后的链表

2、定义blist 记住alist最初的头节点对象，以便从next链中寻找下一个节点

3、使用while循环，(pHead1||pHead2)是指，只有两个都执行到末尾节点时，才会跳出循环。

4、while循环体的前两个if语句是考虑到链表不一定都是等长的，有一个执行完了，另一个没执行完的时候，就直接把剩余的添加进alist链表中。

5、当两个链表均不为空，就可以进行数值比较了，更小的数值先加入alist链表，添加完之后就挪自身next指针移到下一个节点，而alist本身也要指向自身链表的最新那个指针，方便后面的新数据添加进来。

6、循环体执行完毕，要注意，return回来的值不是blist，而是blist.next，因为最初初始化 let alist = new ListNode(null); 添加了一个null值的头结点，之后的添加操作并没有改变这个val为null的头结点， blist链表头节点中next指向的数据才是新添加的排序完成的新数据。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2){
    // write code here
    let alist = new ListNode(null);
    let blist = alist; // 记住alist的最初位置
    while(pHead1||pHead2){
		if(pHead1 === null){
			alist.next = pHead2;
			pHead2 = pHead2.next;
			alist = alist.next;
		}else if(pHead2 === null){
			alist.next = pHead1;
			pHead1 = pHead1.next;
			alist = alist.next;
		}else{
			if(pHead1.val < pHead2.val){
				alist.next = pHead1;
				pHead1 = pHead1.next;
				alist = alist.next;
			}else{
				alist.next = pHead2;
				pHead2 = pHead2.next;
				alist = alist.next;
			}
		}
	}
	return blist.next;
}