昨天我们回顾了 链表的一些基础操作, 今天我们一起来看下几道链表的经典题目, 来巩固对链表的认识和理解。
本期题目总揽;
1. #141 环形链表 |
2. #142 环形链表 ||
3. #19 删除链表的倒数第N个节点
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
解法1: Set
我们可以利用set这个数据结构来解决这道题,首先定义一个Set。
之后遍历链表的节点,每遍历一个节点,就将这个节点的元素放入set中,如果这个链表没有环,那么最终遍历就结束了。
如果链表有环的话,那么肯定有一个元素会被访问两次,当第二次访问这个元素的时候,set中就有记录了,这样就可以判断出链表是否有环了。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
while(head) {
if(head.hasVisited) {
return true
}
head.hasVisited = true
head = head.next
}
return false
};
解法2: 快慢指针
假设有个圆形的操场,操场上有a和b两个人。
a和b最开始的时候是站在一起的:
b的速度是a的一倍,b不停的跑把a甩在身后了:
b跑了N圈之后,终于追上a了:
按照这个思路,我们可以假设有a和b两个指针,一个慢一个快,如果链表是有环状的,那么走的快的那个指针迟早会跟慢指针重合的:
代码实现:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
var fast = slow = head
while (slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if(slow === fast) {
return true
}
}
return false
};
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
这道题和上道题是十分类似, 不同的是返回值。
这道题要返回的是, 入环的那个节点。
解法1: Set
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if(!head || !head.next) return null
var set = new Set()
while(head) {
if(!set.has(head)) {
set.add(head)
head = head.next
} else {
return head
}
}
return null
};
解法2: 快慢指针
说一下算法思路:
1. 先用快慢指针, 找到他们相遇点(如果存在环)
2. 再重新从链表头,以及相遇点开始, 两个位置一起走, 再次相遇就是环的入口。
有三个节点需要注意:
我们要证明 : 初始点到环的入口的 步数 等于 相遇点到环入口的步数
令:初始点到入口为 s, 入口到相遇点 m, 环的周长为 r
我们只需证明: s == r - m
首先我们假设:
慢指针走了 k 步到相遇点, 那么快指针就是 2k 步
所以我们已有的条件:
条件1: 2k - k = nr 即 k = nr。(慢指针还没到环,快指针已经转了好几圈)
条件2: s = k - m
把 1 代入 2 得 :
s = nr - m
等价变形得:s == (n - 1) r + (r - m)
得证。
代码实现:
var detectCycle = function(head) {
if(!head || !head.next) return null
var fast = head
var slow = head
var has_cycle = false
while(fast && fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
if(fast == slow) {
has_cycle = true
break
}
}
if(has_cycle) {
// 再重新从链表头,以及相遇点开始,
// 两个位置一起走, 再次相遇就是环的入口。
fast = head
while(fast != slow) {
fast = fast.next
slow = slow.next
}
// fast == slow 的时候, 即找到了入环点
return fast
}
return null
};
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
我们可以设想假设设定了双指针p和q
当q指向末尾的NULL,p与q之间相隔的元素个数为n时,
那么删除掉p的下一个指针就完成了要求。
[此动图摘自https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/ ]
代码实现:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
var dummyHead = new ListNode(0)
dummyHead.next = head
var p = dummyHead
var q = dummyHead
for(var i = 0; i < n + 1; i++) {
q = q.next
}
while(q) {
p = p.next
q = q.next
}
var delNode = p.next
p.next = delNode.next
delNode = null // 释放delNode
var retNode = dummyHead.next
dummyHead = null // 释放dummyHead
return retNode
};
总结
今天这三道题都是简单的链表操作, 配合示意图,十分的容易理解。
我们下期再见。