js数据结构之链表附力扣算法题

链表是什么

• 多个元素组成的元素
• 元素存储不连续，用next指针连在一起
• 原型链的本质就是链表

数组和链表的区别

• 数组：增删非首尾元素时往往需要移动元素
• 链表：增删非首尾元素，不需要移动元素，只需要更改next的指向即可
• javascript中没有链表
• 可以用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
// 以上代码已经创建了一条大链表

// 操作链表
// 1遍历链表
let p =a;
while(p){
	console.log(p.val) // a b c d
	p = p.next
}

// 2链表中插入值
const e = {val: '3'} // 插入c d之间
c.next = e
e.next = d

// 3删除
c.next = d; // 此时链表中e已经被删除

力扣 237:删除链表中的节点

237 解题思路

• 无法直接获取被删除节点的上个节点
• 将被删除节点转移到下个节点（例如 4，5，1，9 想删除1，只需要把1的下个节点赋值到本节点，变成4，5，9，9 在删除下个节点9即可实现删除本节点）

// 解题步骤
var deleteNode = function(node){
	node.val = node.next.val
	node.next = node.next.next
}

力扣 206:反转链表

206 解题思路

• 反转两个节点：将n+1的next指向n
• 反转多个节点：双指针遍历链表，重复以上操作

// 双指针一前一后遍历链表
// 反转双指针
// 有点绕 多看几遍
var reverseList = function(head){
   let p1 = head;
   let p2 = null;
   while(p1) {
   	const tmp = p1.next
   	p1.next = p2
   	p2 = p1;
   	p1 = tmp;
   }
   return p2 // 注意此处返回p2
}

力扣 2:两个数相加

2 解题思路

• 数学题，模拟相加操作
• 需要遍历链表

// 新建一个空链表
// 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加
// 时间复杂度 O(n);空间复杂度也是O(n)
var addTwoNumber = function(l1, l2){
	const l3 = new ListNode(0);
	let p1 = l1; // 一个指针指向一个链表的头部
	let p2 = l2; // 另一个指针指向另一个链表的头部
	let p3 = l3;
	let carry = 0 // 进位的数字
	while(p1 || p2) {
		const v1 = p1 ? p1.val : 0;
		const v2 = p2 ? p2.val : 0;
		const val = v1 + v2 + carry;
		carry = Math.floor(val / 10);
		p3.next = new ListNode(val % 10);
		if (p1) p1 = p1.next;
		if (p2) p2 = p2.next;
		p3 = p3.next
	}
	if (carry) {
		p3.next = new ListNode(carry)
	}
	return l3.next
}

力扣 83:删除排序链表中的重复元素

83 解题思路

• 因为链表是有序的，所有重复元素一定相邻
• 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值

// 时间复杂度O(n) 空间复杂赋O(1)
function deleHandle (head){
	let p = head;
	while(p && p.next) {
		if (p.val === p.next.val) {
			p.next = p.next.next;
		} else {
			// 注意此行代码 放在else中，避免三个相同的元素一同出现
			p = p.next;
		}
	};
	return head;
}

力扣141 环形链表

141 解题思路

• 两人在圆形跑道同时起跑，速度快的一定会超过慢的一人
• 用一块一慢两个指针遍历链表，如果指针能够相逢，那么链表就有环

// 时间复杂度O(n) 空间复杂赋O(1)
function hasCycle (head) {
	let p1 = head;
	let p2 = head; // 快的指针
	while(p1 && p2 && p2.next) {
		p1 = p1.next;
		p2 = p2.next.next;
		if (p1 === p2) {
			return true
		}
	}
}