算法练习笔记（三）

10.19

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

思路:

处理链表的本质，是处理链表结点之间的指针关系。

由一根“针”比较l1和l2的节点值，将它们相继串起来。

最后还要考虑 l1 和 l2 两个链表长度不等的情况：若其中一个链表已经完全被串进新链表里了，而另一个链表还有剩余结点，考虑到该链表本身就是有序的，可以直接把它整个拼到目标链表的尾部。

代码:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoList = function(l1,l2){
	//head头指针，head.next始终指向要返回的链表头
	let head = new ListNode()
	//尾指针，始终指向链表尾部
	let cur = head
	while(l1&&l2){
		if(l1.val<=l2.val){
			cur.next = l1
			l1 = l1.next
		}else{
			cur.next = l2
			l2 = l2.next
		}
		cur = cur.next
	}
	cur.next = l1 !== null?l1:l2;
    //返回起始节点
    return head.next;
}

10.20

①环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle

思路:

有两种方法：

①标记法：

每遍历一处结点就设置一个flag，从flag出发，只要能够再回到flag处，那么就意味着，正在遍历一个环形链表。

②快慢指针：

每当慢指针slow前进一步，快指针fast就前进两步。
如果fast最终遇到空指针，说明链表中没有环；
如果fast最终和slow相遇，说明链表中含有环。

代码

①标记法

var hasCycle = function(head){
	//只要结点存在
	while(head){
		//如果flag已经立过了，那么说明环存在
		if(head.flag){
			return true
		}else{
			head.flag = true
			head = head.next
		}
	}
}

②快慢指针

var hasCycle = function(head){
	let slow = head
	let fast = head
	while(fast&&fast.next){
		slow = slow.next
		fast = fast.next.next
		if(fast === slow){
			return true
		}
	}
	return false
}

②相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路：

本题求的相交起始节点并不是仅仅值相同的节点而是地址相同的节点。

利用双指针分别指向两个链表的头节点，此时有两种情况：

①两表长度相等，每次各走一步，在遍历完链表前，肯定会在相交点前相遇。

②两表不相等，遍历完各自的链表后需要让指针指向另一张表的头节点继续遍历，从而消除两表之间的长度差，慢慢就会变成同时走，如果相交肯定会相遇。

代码:

var getIntersectionNode = function(headA,headB){
	if(headA===null||headB===null){
		return null
	}
	let pA = headA
	let pB = headB
	while(pA!=pB){
		pA = pA === null?headB:pA.next
		pB = pB === null?headA:pB.next
	}
	return pA
}

10.21

①反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list

思路:

需要用到三个指针，分别指向目标结点(cur)、目标结点的前驱结点(pre)、目标结点的后继结点(next)

只需要将cur.next = pre就做到了next指针的反转

代码:

var reverseList = function(head){
	//初始化前驱结点
	let pre = null
	//初始化目标结点
	let cur = head
	//只要目标结点不为null,遍历就得继续
	while(cur!==null){
		//记录目标结点的后继结点
		let next = cur.next
		//反转指针
		cur.next = pre
		//pre往前走一步
		pre = cur
		//cur往前走一步
		cur = next
	}
	//反转结束后，pre就会变成新链表的头节点
	return pre
}

②删除链表中的节点

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list

思路：

参数只给了 要被删除的节点。所以只能通过整容取代它的后继结点达到删除的效果

代码：

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

10.22

①两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

代码

var addTwoNumbers = function(l1,l2){
	//记录进位信息
	let addOne = 0
	//创建链表用于保存结果
	let sum = new ListNode()
	//head永远指向结果链表最开端，用于最后的返回
	let head = sum
	while(l1||l2||addOne){
		let v1 = l1 !==null?l1.val:0
		let v2 = l2 !==null?l2.val:0
		//相加结果
		let r = v1+v2+addOne
		//更新进位信息
		addOne = r>=10?1:0
		//将值保存进链表
		sum.next = new ListNode(r%10)
		//指向下一个节点
		sum = sum.next
		if(l1)l1=l1.next
		if(l2)l2=l2.next
	}
	return head.next
}

②删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

思路:

使用快慢指针。通过快指针先行n步，接着快慢指针一起前进，使得两个指针的差值保持在了"n"上，这样当快指针走到链表末尾（第len个）时，慢指针刚好就在len-n这个地方，也就是倒数第n个结点的前一个结点，这样就可以基于慢指针来做删除。

代码:

var removeNthFromEnd = function(head,n){
	//dummy结点可以处理掉头结点为空的边界问题
	const dummy = new ListNode()
	dummy.next = head
	let slow = dummy
	let fast = dummy
	//fast指针闷头走n步
	while(n>0){
		fast = fast.next
		n--
	}
	//快慢指针一起走
	while(fast.next){
		fast = fast.next
		n--
	}
	//慢指针删除自己的后继节点
	slow.next = slow.next.next
	return dummy.next
}

10.23

①复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer

代码：

var copyRandomList = function(head){
	if(!head) return head
	let cur = head
	const map = new Map()
	//第一次遍历，生成一个具有val属性的链表
	while(cur){
		map.set(cur,new Node(cur.val))
		cur = cur.next
	}
	//第二次遍历，根据映射关系，将random和next指向对应的节点或者null
	cur = head
	while(cur){
		map.get(cur).next = map.get(cur.next)||null
		map.get(cur).random = map.get(cur.random)||null
		cur = cur.next
	}
	return map.get(head)
}

②LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

思路：

参考

https://leetcode-cn.com/problems/lru-cache/solution/javascript-es6-map-jian-dan-shi-xian-by-muyids/

代码

var LRUCache = function(capacity){
	this.capacity = capacity
	this.cache = new Map()
}
LRUCache.prototype.get = function(key){
	let cache = this.cache
	if(cache.has(key)){
		let temp = cache.get(key)
		cache.delete(key)
		cache.set(key,temp)
		return temp
	}else{
		return -1
	}
}
LRUCache.prototype.put = function(key,value){
	let cache = this.cache
	if(cache.has(key)){
		cache.delete(key)
	}else if(cache.size>=this.capacity){
		cache.delete(cache.keys().next().value)
	}
	cache.set(key,value)
}

10.24

①排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list

思路：

遍历链表组成数组，然后数组排序，重新组成新链表

代码：

var sortList = function(head){
	const dummy = new ListNode()
	let pre = dummy
	let stack = []
	while(head){
		stack.push(head.val)
		head = head.next
	}
	stack = stack.sort((a,b)=>a-b)
	for(let i=0;i<stack.length;i++){
		pre.next = new ListNode(stack[i])
		pre = pre.next
	}
	return dummy.next
}

②奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/odd-even-linked-list

思路：

使用双指针：奇指针遍历链表中的奇数位节点，偶指针遍历链表中的偶数位节点，最后将偶指针遍历的偶数位节点连接在奇指针链表末尾。

代码:

var oddEvenList = function(head){
    if(!head||!head.next)return head
    //奇偶指针
    let oddp = head
    let evenp = head.next
    //定义指向偶指针链表的头结点，用于后续连接
    let evenHead = evenp
    while(evenp!==null&&evenp.next!==null){
        oddp.next = oddp.next.next
        oddp = oddp.next
        evenp.next = evenp.next.next
        evenp = evenp.next
    }
    //奇数节点连接偶数节点
    oddp.next = evenHead
    return head
}