点赞关注，不再迷路，你的支持对我意义重大！
🔥 Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见 已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）
前言
- 链表相交 & 成环问题可以归为一类问题，在面试中出现频率较高；
- 在这篇文章里，我将梳理链表相交 & 成环问题的解法。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
| 相关问题 | 提示 & 题解 |
|---|---|
|
160. 相交链表 Intersection of Two Linked Lists |
【题解】 |
|
141. 环形链表 Linked List Cycle |
【题解】 |
|
142. 环形链表 II Linked List Cycle II |
【题解】 |
|
61. 旋转链表 Rotate List |
【题解】 |
|
（扩展）457. 环形循环数组 Circular Array Loop |
【题解】 |
目录
1. 判断链表相交
160. Intersection of Two Linked Lists 相交链表 【题解】
编写一个程序，找到两个单链表相交的起始节点。
解法1：哈希表
class Solution {
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
if (null == headA || null == headB) {
return null
}
val set = HashSet<ListNode>()
var pA = headA
var pB = headB
while (null != pA) {
set.add(pA)
pA = pA.next
}
while (null != pB) {
if (set.contains(pB)) {
return pB
}
pB = pB.next
}
return null
}
}
复杂度分析：
- 时间复杂度：两个链表的节点最多访问一次，时间复杂度为
- 空间复杂度：以其中一个链表构建哈希表，空间复杂度为
解法2：链表成环
class Solution {
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
if (null == headA || null == headB) {
return null
}
var pA = headA
var pB = headB
while (pA != pB) {
// 退出的关键是：pA和pB指向同一个指针（不是值相等），或者都指向null
pA = if (null == pA) headB else pA.next
pB = if (null == pB) headA else pB.next
}
return pA
}
}
复杂度分析：
- 时间复杂度：两个链表的节点最多访问一次，时间复杂度为
- 空间复杂度：只是用了常量级别变量，空间复杂度为
2. 判断链表成环
141. Linked List Cycle 环形链表 【题解】
给定一个链表，判断链表中是否有环。
解法1：哈希表
class Solution {
fun hasCycle(head: ListNode?): Boolean {
val set = HashSet<ListNode>()
var p = head
while (null != p) {
if (set.contains(p)) {
return true
}
set.add(p)
p = p.next
}
return false
}
}
复杂度分析：
- 时间复杂度：链表的节点最多访问一次，时间复杂度为
- 空间复杂度：哈希表空间复杂度为
解法2：Floyd 判圈算法
class Solution {
fun hasCycle(head: ListNode?): Boolean {
var slow = head
var fast = head
while (null != fast && null != fast.next) {
slow = slow!!.next
fast = fast.next!!.next
if (slow == fast) {
return true
}
}
return false
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：只是用了常量级别变量，空间复杂度为
3. 判断链表成环起点
142. Linked List Cycle II 环形链表 II 【题解】
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。不允许修改给定的链表。
解法1：哈希表
与 **第二节类似**，略
解法2：Floyd 判圈算法
class Solution {
fun detectCycle(head: ListNode?): ListNode? {
// 1. 寻找双指针相交位置
var slow = head
var fast = head
var intersect: ListNode? = null
while (null != fast && null != fast.next) {
slow = slow!!.next
fast = fast.next!!.next
if (slow == fast) {
intersect = slow
break
}
}
// 2. 寻找成环位置
if (null == intersect) {
return null
} else {
var p = intersect
var q = head
while (p != q) {
p = p!!.next
q = q!!.next
}
return p
}
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：只是用了常量级别变量，空间复杂度为
4. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
解法1：链表成环
先将链表闭合成环，再找到新表头，断开前驱节点的连接。需要注意 k 大于链表长度的情况
class Solution {
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (null == head || null == head.next || 0 == k) {
return head
}
var cur = head
// 1. 找到尾节点
var count = 1
while (null != cur!!.next) {
cur = cur.next
count++
}
if (0 == k % count) {
// 旋转后未变化
return head
}
// 2. 链表成环
cur.next = head
// 3. 找到倒数第 k 个节点的前驱节点
cur = head
for (index in 0 until count - (k % count) - 1) {
cur = cur!!.next
}
// 4. 断开 preK
val preK = cur
val kP = preK!!.next
preK.next = null
return kP
}
}
复杂度分析：
- 时间复杂度：扫描两趟，时间复杂度为
- 空间复杂度：使用了常量级别变量，空间复杂度为
5. (扩展) 判断环形循环数组
457. Circular Array Loop 环形循环数组 【题解】
给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
解法1：哈希表 + 记忆化
class Solution {
fun circularArrayLoop(nums: IntArray): Boolean {
val visits = BooleanArray(nums.size) { false }
fun isCircle(from: Int): Boolean {
if (visits[from]) {
return false
}
val set = HashSet<Int>()
var cur = from
while (true) {
// 路径标志
visits[cur] = true
val nextIndex = nums.jump(cur)
if (nums[nextIndex] * nums[cur] < 0) {
// 逆向
return false
}
if (set.contains(cur)) {
return cur != nextIndex
}
set.add(cur)
cur = nextIndex
}
}
for (index in 0 until nums.size) {
if (isCircle(index)) {
return true
}
}
return false
}
/**
* @return index of next jump
*/
fun IntArray.jump(curIndex: Int): Int {
val nextIndex = curIndex + this[curIndex] % size
if (nextIndex < 0) {
return size + nextIndex
}
if (nextIndex >= size) {
return nextIndex - size
}
return nextIndex
}
}
复杂度分析：
- 时间复杂度：每个位置最多访问一次，时间复杂度为
- 空间复杂度：哈希表为
路径标志为
，总体为
解法2：快慢指针
创作不易，你的「三连」是丑丑最大的动力，我们下次见！
