[第29期] 熟悉链表的几个经典题目- #141，#142， #19
[第29期] 熟悉链表的几个经典题目- #141，#142， #19
昨天我们回顾了 链表的一些基础操作， 今天我们一起来看下几道链表的经典题目， 来巩固对链表的认识和理解。
本期题目总揽；
1. #141 环形链表 |
2. #142 环形链表 ||
3. #19 删除链表的倒数第N个节点
141. 环形链表|
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 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
};142. 环形链表||
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 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. 再重新从链表头,以及相遇点开始, 两个位置一起走, 再次相遇就是环的入口。
有三个节点需要注意:
- 起始节点
- 环的入口节点(即：上图中的结点3)
- 相遇的节点(即：上图中的结点4)
我们要证明 : 初始点到环的入口的 步数 等于 相遇点到环入口的步数
令：初始点到入口为 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
};16. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.我们可以设想假设设定了双指针p和q
当q指向末尾的NULL，p与q之间相隔的元素个数为n时，
那么删除掉p的下一个指针就完成了要求。
- 设置虚拟节点dummyHead指向head
- 设定双指针p和q，初始都指向虚拟节点dummyHead
- 移动q，直到p与q之间相隔的元素个数为n
- 同时移动p与q，直到q指向的为NULL
- 将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
};
总结
今天这三道题都是简单的链表操作， 配合示意图，十分的容易理解。
我们下期再见。