五个经典链表OJ题带你进阶C++链表篇

五个经典链表OJ题带你进阶C++链表篇

前言

链表作为一种非常重要的数据结构，常常用来解决一些实际问题。在代码中，我们需要用到链表时，不能只是会使用，而是要掌握它的一些经典问题，才能真正了解链表的一些相关性质和应用。本篇攻略介绍了五个经典的链表OJ题，通过解析这些问题，帮助初学者进阶学习C++链表。

问题一：求链表的长度

输入一个单链表，输出链表的长度。

算法描述：

1. 定义一个计数器count，初始值为0
2. 从头节点开始，遍历链表
3. 每经过一个节点，计数器+1
4. 遍历完整个链表后，返回count的值

代码实现：

int getLength(ListNode* head) {
    int count = 0;
    ListNode* cur = head;
    while (cur != nullptr) {
        count++;
        cur = cur->next;
    }
    return count;
}

问题二：链表的倒数第K个节点

输入一个单链表，输出该链表的倒数第K个节点。假设该链表的长度未知，但是保证k不大于链表的长度。

算法描述：

1. 使用双指针法，定义fast指针和slow指针
2. fast指针先向前移动k步，此时，slow指针和fast指针之间的距离为k
3. 同时移动slow指针和fast指针，直到fast指针指向链表的最后一个节点
4. 返回slow指针指向的节点即可

代码实现：

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (k > 0 && fast != nullptr) {
        fast = fast->next;
        k--;
    }
    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

示例：假设链表为1->2->3->4->5，k=2。

1. fast指针先向前移动2步，此时fast指针指向3，slow指针指向1
2. 同时移动slow指针和fast指针，当fast指针指向5时，slow指针指向4
3. 返回slow指针指向的节点4

问题三：翻转链表

输入一个单链表的头节点，反转该链表并输出反转后链表的头节点。

算法描述：

1. 定义三个指针：pre指向前一个节点，cur指向当前节点，temp指向当前节点的下一个节点
2. 遍历链表，同时在遍历的过程中进行指针的修改
3. 每次修改完指针之后pre指针和cur指针同时向前移动一位，temp指针指向cur指针的下一个节点
4. 遍历结束后，返回pre指针即可

代码实现：

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

示例：假设链表为1->2->3->4->5。

1. 初始时，pre指针为空，cur指针指向1，temp指针指向2
2. 当前指针cur指向的节点1，它的下一个节点指向pre节点（pre节点为空）
3. 同时，pre指针指向了cur指针指向的节点1，cur指针指向了temp指针所指向的下一个节点2
4. 第一次循环结束，链表变成了2->1->null
5. 重复2-4步骤，直到遍历完整个链表，返回pre指针指向的节点5。

问题四：链表删除操作

输入一个单链表和要删除的节点所在的指针，将该指针指向的节点从链表中删除并返回链表的头节点。

算法描述：

1. 如果要删除的是头节点，直接返回head->next
2. 找到要删除节点的前一个节点pre
3. 将pre的next指向要删除节点的下一个节点
4. 返回head指针即可

代码实现：

ListNode* deleteNode(ListNode* head, ListNode* node) {
    if (head == node) {
        return head->next;
    }
    ListNode* cur = head;
    while (cur->next != nullptr && cur->next != node) {
        cur = cur->next;
    }
    if (cur->next == node) {
        cur->next = node->next;
    }
    return head;
}

问题五：判断链表是否有环

给定一个链表，判断链表中是否有环。

算法描述：

1. 定义快指针fast和慢指针slow，将它们初始指向链表的头节点
2. fast指针每次移动两步，slow指针每次移动一步
3. 在遍历的过程中，如果快指针指向了nullptr，说明链表无环；如果快指针和慢指针指向的是同一个节点，那么链表有环
4. 返回布尔值即可

代码实现：

bool hasCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

以上就是五个经典链表OJ题的完整攻略。通过对这些问题的解析，可以帮助初学者进阶C++链表，提高自己的编程水平。