LeetCode：经典题之141、142 题解及延伸

系列目录

88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表

141. 环形链表

🌟链表+哈希表+快慢指针

原题链接

C++
若未特殊标明，以下题解均写用C++

方法一 哈希表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 无序集合(哈希集合) 变量类型为 ListNode*
        // 检查节点是否访问过
        unordered_set<ListNode*> seen;
        // head 不为空
        while (head) {
            // 这里 count的返回值只能是 0或1
            // 不能写成 seen.count(head) != null
            if (seen.count(head) != 0)
                return true;

            // 节点不存在， 存入——seen.insert();
            // 避免无限循环导致超时
            seen.insert(head);
            head = head->next;        
        }

        return false;
    }
};

方法二 快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 如果 链表长度为0或1
        if (head == nullptr || head->next == nullptr)
            return false;

        ListNode* slow = head;
        ListNode* fast = head->next;

        while (slow != fast) {
            // 一定要先检查节点本身，避免出现 未定义行为
            // 链表长度为2
            if (fast == nullptr || fast->next == nullptr )
                return false;

            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

⚠️小细节：要先检查节点本身，再检查它的next

为什么 fast == nullptr 不能和 fast->next == nullptr 调换位置？

如果调换位置，先检查 fast->next == nullptr，当链表中只有一个节点时(即 head 是唯一节点)，fast 将会是 head->next，它将是 nullptr

在这种情况下，fast->next 的检查(即 nullptr->next)将会导致一个未定义行为(通常是一个运行时错误)，因为你不能在 nullptr 上解引用

所以，首先检查 fast == nullptr 是为了确保在尝试访问 fast->next 之前，fast 不是 nullptr 这样可以避免未定义行为

方法一时间复杂度O(N) 空间复杂度O(N) 其中N为链表节点数

在这里插入图片描述

方法二时间复杂度O(N) 空间复杂度O(1) 其中N为链表节点数

在这里插入图片描述

“相同”时间复杂度的两种算法，为什么实际执行时间差别这么大呢？

在实践中，快慢指针方法通常具有较小的常数因子，因为它只涉及指针操作和比较
虽然哈希表理论上的查找、插入的时间复杂度为O(1)——准确的说应该是平均O(1)
哈希表方法在插入和查找元素时可能需要进行哈希计算，这可能会引入额外的计算开销
但与其他数据结构相比，哈希表还是十分高效的，不必过于纠结

我们引入常量因子的概念

参考自《算法导论》

在这里插入图片描述

常量因子

又称常数因子

在C++代码中，常数因子经常以字面常量、const变量或枚举类型的形式出现

这些常数因子可能用于定义数组的大小、循环的次数、数学计算中的系数、物理模拟中的常量等

字面常量

#include <iostream>  
  
int main() {  
    const int arraySize = 100; // 数组大小的常数因子  
    int arr[arraySize]; // 使用字面常量作为数组大小  
  
    // 使用字面常量进行数学计算  
    double result = 3.14159 * 2 * 5; // π乘以直径，其中3.14159是π的近似值  
  
    std::cout << "Array size: " << arraySize << std::endl;  
    std::cout << "Calculation result: " << result << std::endl;  
  
    return 0;  
}

const变量

#include <iostream>  
  
int main() {  
    const double gravity = 9.8; // 重力加速度的常数因子  
  
    double height = 10.0; // 初始高度  
    double time = std::sqrt(2 * height / gravity); // 使用常数因子计算自由落体时间  
  
    std::cout << "Time to fall from " << height << " meters: " << time << " seconds" << std::endl;  
  
    return 0;  
}

枚举类型

#include <iostream>  
  
enum class Color {  
    RED = 1,     // 颜色常量的一个值  
    GREEN = 2,  
    BLUE = 3  
};  
  
int main() {  
    Color myColor = Color::RED; // 使用枚举常量  
    switch (myColor) {  
        case Color::RED:  
            std::cout << "The color is red." << std::endl;  
            break;  
        // ... 其他情况 ...  
    }  
  
    return 0;  
}

魔法数字(Magic Numbers)

在代码中直接使用字面常量而不是给它们命名可能会导致代码难以理解和维护
这些字面常量通常被称为“魔法数字” 为了改进代码的可读性和可维护性，最好将魔法数字替换为具有描述性名称的const变量或枚举常量

性能优化中的常数因子

在性能优化的场景中，常数因子可能会变得很重要
例如，如果一个循环体内部有一个操作非常耗时，而这个操作是固定的(即不随循环迭代而变化)，那么减少这个操作的执行次数(即减少常数因子)可能会显著提高性能

// 假设有一个耗时的操作doExpensiveOperation()  
for (int i = 0; i < 1000; ++i) { // 这里的1000是一个常数因子  
    doExpensiveOperation(); // 假设这个操作非常耗时  
}  
  
// 优化：如果可能的话，减少循环次数(即减少常数因子)  
const int optimizedIterations = 500; // 假设这是优化后的常数因子  
for (int i = 0; i < optimizedIterations; ++i) {  
    doExpensiveOperation();  
}

在上面的例子中，通过减少循环次数(即减少常数因子)，我们可能能够显著提高代码的性能
但是，这种优化要在确保算法正确性和满足性能需求的前提下进行

142. 环型链表II

🌟链表+哈希表+快慢指针

原题链接

C++
若未特殊标明，以下题解均写用C++

方法一 哈希表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head) {
            if (seen.count(head) != 0)
                // pos 不作为参数传递
                return head;
            seen.insert(head);
            head = head->next;
        }

        return nullptr;
    }
};

方法二 快慢指针

图示：

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        // 若没有环，fast 比 slow先指向空
        // 以此作为while 的循环条件判定
        while (fast) {
            // 如果链表长度为 1
            if (fast->next == nullptr)
                return nullptr;

            slow = slow->next;
            fast = fast->next->next;
            // 此时定义 *pre
            if (fast == slow) {
                ListNode *pre = head;
                while (pre != slow) {    
                    pre = pre->next;
                    slow = slow->next;
                }

                return pre;
            }  
        }

        // 直到 fast指向空都没能满足 slow = fast
        return nullptr;
    }
};