LeetCode：经典题之61、160、83题解与拓展

系列目录

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

61.旋转链表

🌟链表

原题链接

图示：
辅助代码一同理解效果更佳

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr)
            return head;

        // iterator/iteration 迭代器/迭代
        // 在这里是一种遍历指针
        ListNode* iter = head;
        int n = 1;
        while (iter->next) {
            iter = iter->next;
            n ++;
        }

        // 先模运算，再相减
        int add = n - k % n;
        // k 为n的倍数，无需进行任何操作
        if (add == n)
            return head;

        // 构造"环"链表
        iter->next = head;    
        while (add --) 
            iter = iter->next;
        
        ListNode* ans = iter->next;
        // 拆除"环"链表
        iter->next = nullptr;

        return ans;
    }
};

再来试试下面这道有意思的相交链表题吧～

160.相交链表

🌟链表

原题链接

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 定义两个指针A B，让他俩移动，headA和headB留在原理用于做标记
        ListNode *A = headA, *B = headB;
        // ListNode* A = headA;
        // ListNode* B = headB;

        // 三元条件操作符 条件 A != nullptr为真，执行冒号前的语句，否则冒号后
        while (A != B) {
            // 指针A 走完了单链表A，再走B 共走了a + (b - c)
            A = A != nullptr? A->next : headB;
            // 指针B 走完了单链表B，再走A 共走了b + (a - c)
            B = B != nullptr? B->next : headA;
        }

        return A;
    }
};

A = A != nullptr ? A->next : headB

这是一条三元条件操作符 语句
若条件A != nullptr为真，则执行冒号前的语句，否则执行冒号后

三元条件运算符

又称条件运算符，它允许在单个表达式中测试一个条件，并根据该条件的结果返回两个值中的一个 这个运算符由问号(?)和冒号(:)组成，其形式如下：

condition ? value_if_true : value_if_false

• condition 是一个布尔表达式，其结果必须是 true 或 false
• value_if_true 是当 condition 为 true 时返回的值
• value_if_false 是当 condition 为 false 时返回的值

示例

假设我们有两个整数 a 和 b，我们想找出它们中的较大者并赋值给变量 max 使用三元条件运算符，我们可以这样做：

int a = 5;  
int b = 10;  
int max = (a > b) ? a : b; // max 现在是 10

在这个例子中，我们检查 a > b 这个条件 因为 5 > 10 是 false，所以 max 被赋值为 b 的值，即 10

再举一个链表的例子，假设我们有两个链表 listA 和 listB，我们有一个指针 current 指向 listA 的某个节点，我们想要将 current 移动到下一个节点，但如果 current 是空的(nullptr)，我们想要将 current 指向 listB 的头节点 headB：

ListNode* current = /* 指向 listA 的某个节点 */;  
ListNode* headB = /* listB 的头节点 */;  
current = (current != nullptr) ? current->next : headB;

在这个例子中，如果 current 不为空，则 current 被更新为其 next 指针所指向的节点；如果 current 为空，则 current 被赋值为 headB

下面这是一道链表中常出现的构造“哨兵” 的经典题～

83.删除排序链表中的重复元素

🌟链表

原题链接

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // == 判断 = 赋值
        if (!head)
            return head;
		
        // 这里的 head 起到哨兵💂的作用——“站岗”不动
        // 维护(preserve)一个指针prev
        // 或是定义一个cur(cursor,游标)，调整它的next指针
        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val)
                cur->next = cur->next->next;

            else cur = cur->next;
        }

        return head;
    }
};

哨兵

哨兵 (Sentinel)，又称哑节点 (Dummy Node)或虚拟头节点
是一个常用的技术，用于简化链表的边界条件处理 哨兵是一个特殊的节点，它通常不存储实际的数据，而是被放置在链表的前面或后面，作为链表的一个固定参照点

使用哨兵的优点：

1. 简化边界条件处理：由于哨兵的存在，我们不需要在每次操作链表时都检查头节点或尾节点是否为空
2. 减少空指针检查：由于我们可以始终从哨兵节点开始遍历链表，因此我们不需要在遍历时担心空指针的问题

哨兵节点的具体使用：

假设我们有一个简单的单链表实现，每个节点都有一个整数值和一个指向下一个节点的指针 我们可以使用哨兵节点来简化这个链表的实现

链表节点定义：

struct ListNode {  
    int val;  
    ListNode *next;  
    ListNode(int x) : val(x), next(nullptr) {}  
};

使用哨兵节点的链表实现：

class LinkedListWithSentinel {  
private:  
    ListNode *sentinel; // 哨兵节点  
  
public:  
    LinkedListWithSentinel() {  
        sentinel = new ListNode(0); // 创建一个哨兵节点，值通常为0或特殊值  
    }  
  
    ~LinkedListWithSentinel() {  
        // 需要遍历链表并逐个删除节点，包括哨兵节点  
        ListNode *current = sentinel;  
        while (current != nullptr) {  
            ListNode *next = current->next;  
            delete current;  
            current = next;  
        }  
    }  
  
    // 在链表尾部添加节点  
    void append(int val) {  
        ListNode *newNode = new ListNode(val);  
        ListNode *current = sentinel;  
        while (current->next != nullptr) {  
            current = current->next;  
        }  
        current->next = newNode;  
    }  
  
    // 省略其他链表操作，如删除、查找等...  
  
    // 示例：遍历链表并打印节点值  
    void printList() {  
        ListNode *current = sentinel->next; // 从哨兵节点的下一个节点开始遍历  
        while (current != nullptr) {  
            std::cout << current->val << " ";  
            current = current->next;  
        }  
        std::cout << std::endl;  
    }  
};

在上面的代码中，sentinel 是链表的哨兵节点 当我们想要向链表添加新节点时，我们总是从哨兵节点开始遍历，直到找到链表的末尾 (即 current->next == nullptr ) 当我们想要遍历链表时，我们也总是从 sentinel->next 开始，这样可以避免检查头节点是否为空

使用哨兵节点可以大大简化链表的边界条件处理，使代码更加清晰和易于维护
然而，它也增加了额外的空间开销 (一个哨兵节点的内存 )，但通常这种开销是可以接受的，
特别是当链表的操作频繁且边界条件复杂时