链表

1、反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

1.1、问题描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1
输入：
返回值：
示例2
输入：{}
返回值：{}
说明：空链表则输出空

1.2、思路及代码

方法一：迭代法

初始化两个指针，prev用于记录前一个节点，current用于遍历链表。然后，我们使用一个循环来逐一反转链表中的节点，将当前节点的next指针指向前一个节点，同时更新prev和current指针。最终，prev指向的就是新链表的头节点。

#include <iostream>

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前一个节点为nullptr
    ListNode* current = head; // 初始化当前节点为链表头节点

    while (current != nullptr) {
        ListNode* nextNode = current->next; // 保存下一个节点
        current->next = prev; // 反转当前节点的next指针，指向前一个节点
        prev = current; // 更新prev指针
        current = nextNode; // 更新current指针
    }

    return prev; // prev指向新链表的头节点
}

int main() {
    ListNode* pHead = new ListNode(1); // 创建头节点
    pHead->next = new ListNode(2); // 添加节点2
    pHead->next->next = new ListNode(3); // 添加节点3

    std::cout << "原始链表：";
    ListNode* current = pHead;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // 调用反转函数
    ListNode* newHead = reverseList(pHead);

    std::cout << "反转后的链表：";
    current = newHead;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;

    return 0;
}

方法二：递归法

利用递归函数，从链表的尾节点开始不断反转指针。

#include <iostream>

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

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head; // 如果链表为空或只有一个节点，直接返回链表头
    }

    // 递归反转剩余部分
    ListNode* newHead = reverseList(head->next);

    // 更新当前节点的next指针
    head->next->next = head;
    head->next = nullptr;

    return newHead; // 返回新链表的头节点
}

int main() {
    ListNode* pHead = new ListNode(1); // 创建头节点
    pHead->next = new ListNode(2); // 添加节点2
    pHead->next->next = new ListNode(3); // 添加节点3

    std::cout << "原始链表：";
    ListNode* current = pHead;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // 调用反转函数
    ListNode* newHead = reverseList(pHead);

    std::cout << "反转后的链表：";
    current = newHead;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;

    return 0;
}

2、链表内指定区间反转

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

2.1、问题描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度 O(1)。例如：给出的链表为 1→2→3→4→5→NULL,m=2,n=4, 返回 1→4→3→2→5→NULL.

2.2、思路及代码

思路：

首先，创建一个虚拟头节点 dummy，将它连接到原链表的头部，这样可以处理从第一个节点开始反转的情况。
遍历链表找到第 m - 1 个节点，它是反转区间的前一个节点。
将第 m - 1 个节点记为 prev，第 m 个节点记为 start。
使用迭代方法，反转从 start 到 n 的区间。
反转结束后，将 prev 的 next 指针指向反转后的头节点，将 start 的 next 指针指向反转后的尾节点。
返回 dummy->next，即反转后的链表头。

#include <iostream>

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

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (head == nullptr || m == n) {
        return head; // 处理特殊情况
    }

    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    dummy->next = head;
    ListNode* prev = dummy; // prev是反转区间的前一个节点

    // 找到第 m - 1 个节点
    for (int i = 1; i < m; ++i) {
        prev = prev->next;
    }

    // 反转区间的起始节点
    ListNode* start = prev->next;
    ListNode* current = start->next;

    // 反转区间的操作
    for (int i = m; i < n; ++i) {
        start->next = current->next;
        current->next = prev->next;
        prev->next = current;
        current = start->next;
    }

    return dummy->next;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);
    std::cout << "原始链表：";
    printList(head);

    int m = 2, n = 4;
    ListNode* reversedHead = reverseBetween(head, m, n);

    std::cout << "反转后的链表：";
    printList(reversedHead);

    return 0;
}

3、链表中的节点每k个一组翻转

3.1、问题描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样你不能更改节点中的值，只能更改节点本身。

3.2、思路及代码

思路：

首先，计算链表的长度，以确定需要进行多少次 k 个节点的翻转。
创建一个虚拟头节点 dummy 并将其连接到链表的头部，以处理头部可能被翻转的情况。
使用两个指针 start 和 end 来标识每组 k 个节点的开始和结束位置，同时使用一个指针 prev 来标识前一组 k 个节点的尾节点。
在每一组 k 个节点中，将节点的 next 指针进行翻转，即将节点的 next 指向前一个节点。
更新 prev 指针和 start 指针。
重复步骤 4 和步骤 5，直到所有的 k 个节点都被翻转。
最后，将 dummy 的 next 指针指向第一组翻转后的头节点，返回新的链表头。

#include <iostream>

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

ListNode* reverseKGroup(ListNode* head, int k) {
    if (head == nullptr || k == 1) {
        return head; // 处理特殊情况
    }

    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    dummy->next = head;
    ListNode* start = dummy; // 标识每组 k 个节点的开始位置
    ListNode* end = dummy;   // 标识每组 k 个节点的结束位置
    ListNode* prev = dummy;  // 标识前一组 k 个节点的尾节点

    int count = 0; // 计数，用于确定是否有 k 个节点
    while (end->next != nullptr) {
        end = end->next;
        count++;
        if (count == k) {
            ListNode* nextGroupStart = start->next; // 下一组 k 个节点的开始位置
            reverseGroup(start, end); // 反转当前组 k 个节点
            prev->next = end; // 更新前一组 k 个节点的尾节点的 next 指针
            start->next = nextGroupStart; // 更新当前组 k 个节点的头节点的 next 指针
            start = nextGroupStart; // 更新每组 k 个节点的开始位置
            end = start; // 更新每组 k 个节点的结束位置
            count = 0; // 重置计数
        }
    }

    return dummy->next;
}

// 反转一组 k 个节点的函数
void reverseGroup(ListNode* start, ListNode* end) {
    ListNode* prev = start;
    ListNode* current = start->next;
    while (current != end) {
        ListNode* nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }
    start->next = prev;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);
    std::cout << "原始链表：";
    printList(head);

    int k = 2; // 每组 k 个节点进行翻转
    ListNode* reversedHead = reverseKGroup(head, k);

    std::cout << "翻转后的链表：";
    printList(reversedHead);

    return 0;
}

4、合并两个排序的链表

4.1、问题描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1
输入：{1,3,5},
返回值：
示例2
输入：{},{}
返回值：{}
示例3
输入：{-1,2,4},
返回值：

4.2、思路及代码

思路：

创建一个新的虚拟头节点 dummy，它的 next 指针初始化为 nullptr，用于存储合并后的链表。
使用两个指针 p1 和 p2 分别指向两个链表的头节点。
遍历两个链表，比较 p1 和 p2 指向的节点的值，将较小节点接到新链表的尾部。
更新 p1 或 p2 指针，将它指向下一个节点，直到其中一个指针为空。
将剩余链表的部分直接接到新链表的尾部，因为这部分链表已经是有序的。
返回新链表的头部，即 dummy->next。

代码：

#include <iostream>

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    ListNode* current = dummy; // 当前节点

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    // 将剩余链表的部分直接接到新链表的尾部
    if (l1) {
        current->next = l1;
    } else {
        current->next = l2;
    }

    return dummy->next;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values1 = {1, 2, 4};
    std::vector<int> values2 = {1, 3, 4};
    ListNode* l1 = createList(values1);
    ListNode* l2 = createList(values2);
    std::cout << "链表1：";
    printList(l1);
    std::cout << "链表2：";
    printList(l2);

    ListNode* mergedHead = mergeTwoLists(l1, l2);
    std::cout << "合并后的链表：";
    printList(mergedHead);

    return 0;
}

5、合并k个已排序的链表

5.1、问题描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

示例1
输入：[{1,2,3},{4,5,6,7}]
返回值：
示例2
输入：[{1,2},{1,4,5},{6}]
返回值：

5.2、思路及代码

思路：

将 k 个链表划分为两个子问题：合并前半部分和合并后半部分。
对前半部分和后半部分分别递归调用合并操作，得到两个有序链表。
将这两个有序链表合并为一个有序链表。

参考代码：

#include <iostream>
#include <vector>

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return nullptr;
    if (n == 1) return lists[0];

    int mid = n / 2;
    std::vector<ListNode*> left(lists.begin(), lists.begin() + mid);
    std::vector<ListNode*> right(lists.begin() + mid, lists.end());

    ListNode* l1 = mergeKLists(left);
    ListNode* l2 = mergeKLists(right);

    return mergeTwoLists(l1, l2);
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<std::vector<int>> values = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
    std::vector<ListNode*> lists;

    for (const auto& v : values) {
        lists.push_back(createList(v));
    }

    std::cout << "合并前的链表：" << std::endl;
    for (const auto& l : lists) {
        printList(l);
    }

    ListNode* mergedHead = mergeKLists(lists);

    std::cout << "合并后的链表：" << std::endl;
    printList(mergedHead);

    return 0;
}

6、判断链表中是否有环

6.1、问题描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

示例1
输入：{3,2,0,-4},1
返回值：true
说明：
第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2
输入：{1},-1
返回值：false
说明：
第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3
输入：
{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：
true

6.2、思路及代码

思路：

使用两个指针，一个慢指针 slow 和一个快指针 fast，同时从链表的头节点开始遍历链表。
每次迭代，慢指针 slow 移动一步，快指针 fast 移动两步。
如果链表中没有环，快指针 fast 将会先达到链表的末尾，此时可以返回 false。
如果链表中有环，快指针 fast 将会进入环并继续移动，而慢指针 slow 将在某个时刻进入环并与快指针相遇。
如果在遍历过程中快慢指针相遇，则链表中存在环，返回 true。

参考代码：

#include <iostream>

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

bool hasCycle(ListNode* head) {
    if (!head || !head->next) {
        return false; // 链表为空或只有一个节点时没有环
    }

    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;      // 慢指针移动一步
        fast = fast->next->next; // 快指针移动两步

        if (slow == fast) {
            return true; // 快慢指针相遇，说明有环
        }
    }

    return false; // 快指针达到链表末尾，没有环
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values = {3, 2, 0, -4};
    ListNode* head = createList(values);
    std::cout << "链表：";
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    // 设置尾节点的 next 指针指向第二个节点，形成环
    head->next->next->next->next = head->next;

    bool hasCycleResult = hasCycle(head);
    if (hasCycleResult) {
        std::cout << "链表中有环。" << std::endl;
    } else {
        std::cout << "链表中没有环。" << std::endl;
    }

    return 0;
}

7、链表中环的入口结点

7.1、问题描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1
输入：{1,2},
返回值：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2
输入：{1},{}
返回值："null"
说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3
输入：{},
返回值：2
说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

7.2、思路及代码

思路：

使用两个指针，一个慢指针 slow 和一个快指针 fast，同时从链表的头节点开始遍历链表。
每次迭代，慢指针 slow 移动一步，快指针 fast 移动两步。
如果链表中没有环，快指针 fast 将会先达到链表的末尾，此时可以返回 nullptr。
如果链表中有环，快指针 fast 将会进入环并继续移动，而慢指针 slow 将在某个时刻进入环并与快指针相遇。
一旦快慢指针相遇，将其中一个指针重新指向链表的头节点，然后两个指针以相同的速度再次前进。当它们再次相遇时，即为环的入口节点。

参考代码：

#include <iostream>

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

ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) {
        return nullptr; // 链表为空或只有一个节点时没有环
    }

    ListNode* slow = head;
    ListNode* fast = head;

    // 快慢指针相遇的点
    ListNode* meet = nullptr;

    while (fast && fast->next) {
        slow = slow->next;      // 慢指针移动一步
        fast = fast->next->next; // 快指针移动两步

        if (slow == fast) {
            meet = slow; // 快慢指针相遇，有环
            break;
        }
    }

    if (!meet) {
        return nullptr; // 没有环
    }

    // 重新指定一个指针从头节点出发，与相遇点相遇时即为环的入口
    ListNode* entry = head;
    while (entry != meet) {
        entry = entry->next;
        meet = meet->next;
    }

    return entry; // 返回环的入口节点
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);
    std::cout << "链表：";
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    // 设置尾节点的 next 指针指向第二个节点，形成环
    head->next->next->next->next->next = head->next;

    ListNode* entry = detectCycle(head);
    if (entry) {
        std::cout << "链表中有环，环的入口节点的值为 " << entry->val << std::endl;
    } else {
        std::cout << "链表中没有环。" << std::endl;
    }

    return 0;
}

8、链表中倒数最后k个结点

8.1、问题描述

输入一个长度为 n 的链表，设链表中的元素的值为 a(i) ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤10^5，0≤ai≤10^9，0≤k≤10^9

要求：空间复杂度O(n)，时间复杂度O(n)

进阶：空间复杂度O(1)，时间复杂度O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1
输入：{1,2,3,4,5},2
返回值：
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2
输入：{2},8
返回值：{}

8.2、思路及代码

思路：

使用两个指针，一个快指针 fast 和一个慢指针 slow，同时从链表的头节点开始遍历链表。
快指针 fast 先向前移动 k 步，然后慢指针 slow 和快指针 fast 同时向前移动，直到快指针 fast 到达链表的末尾。
此时慢指针 slow 所指的节点就是倒数第 k 个节点。

参考代码：

#include <iostream>

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

ListNode* findKthToTail(ListNode* head, int k) {
    if (!head || k <= 0) {
        return nullptr; // 链表为空或k值无效
    }

    ListNode* fast = head;
    ListNode* slow = head;

    // 快指针先向前移动k步
    for (int i = 0; i < k; ++i) {
        if (fast) {
            fast = fast->next;
        } else {
            return nullptr; // k大于链表长度，无法找到倒数第k个节点
        }
    }

    // 快慢指针同时向前移动，直到快指针到达链表末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow; // 返回倒数第k个节点
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);
    std::cout << "链表：";
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    int k = 2; // 倒数第k个节点的值
    ListNode* result = findKthToTail(head, k);
    if (result) {
        std::cout << "倒数第" << k << "个节点的值为 " << result->val << std::endl;
    } else {
        std::cout << "无法找到倒数第" << k << "个节点。" << std::endl;
    }

    return 0;
}

9、删除链表的倒数第n个节点

9.1、问题描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针例如，

给出的链表为: 1→2→3→4→5, n=2. 删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5

数据范围：链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度O(n) 备注：

题目保证n 一定是有效的

示例1
输入：{1,2},2
返回值：

9.2、思路及代码

思路：

使用两个指针，一个快指针 fast 和一个慢指针 slow，同时从链表的头节点开始遍历链表。
快指针 fast 先向前移动 n+1 步，以确保 fast 和 slow 之间有 n 个节点的距离。
然后，同时移动 fast 和 slow，直到 fast 到达链表的末尾。
此时，slow 所指的节点就是倒数第 n 个节点的前一个节点。
删除倒数第 n 个节点即可。

参考代码：

#include <iostream>

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (!head || n <= 0) {
        return nullptr; // 链表为空或n值无效
    }

    ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点
    dummy->next = head;
    ListNode* fast = dummy;
    ListNode* slow = dummy;

    // 快指针先向前移动n+1步
    for (int i = 0; i < n + 1; ++i) {
        if (fast) {
            fast = fast->next;
        } else {
            return nullptr; // n大于链表长度，无法删除
        }
    }

    // 快慢指针同时向前移动，直到快指针到达链表末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除倒数第n个节点
    ListNode* toBeDeleted = slow->next;
    slow->next = slow->next->next;
    delete toBeDeleted;

    return dummy->next; // 返回新的头节点
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);
    std::cout << "原链表：";
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    int n = 2; // 要删除的倒数第n个节点
    ListNode* result = removeNthFromEnd(head, n);
    std::cout << "删除倒数第" << n << "个节点后的链表：";
    for (ListNode* curr = result; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    return 0;
}

10、两个链表的第一个公共结点

10.1、问题描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

返回值描述：

返回传入的pHead1和pHead2的第一个公共节点，后台会打印以该节点为头节点的链表。

示例1
输入：{1,2,3},{4,5},
返回值：
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入：{1},{2,3},{}
返回值：{}
说明：
2个链表没有公共节点 ,返回null，后台打印{}

10.2、思路及代码

思路：

遍历两个链表，分别计算它们的长度。
让较长的链表的指针向前移动到与较短链表相同长度的位置。
然后，同时移动两个指针，直到它们相遇，相遇点即为第一个公共节点。

参考代码：

#include <iostream>

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

int getLength(ListNode* head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}

ListNode* findFirstCommonNode(ListNode* head1, ListNode* head2) {
    if (!head1 || !head2) {
        return nullptr; // 任何一个链表为空时无公共节点
    }

    int len1 = getLength(head1);
    int len2 = getLength(head2);

    // 让较长的链表指针向前移动到与较短链表相同长度的位置
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; ++i) {
            head1 = head1->next;
        }
    } else {
        for (int i = 0; i < len2 - len1; ++i) {
            head2 = head2->next;
        }
    }

    // 同时移动两个指针，直到它们相遇
    while (head1 != head2) {
        head1 = head1->next;
        head2 = head2->next;
    }

    return head1; // 返回第一个公共节点
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values1 = {1, 2, 3, 4, 5};
    std::vector<int> values2 = {6, 7, 8};

    ListNode* head1 = createList(values1);
    ListNode* head2 = createList(values2);

    // 构造公共节点
    ListNode* commonNode = new ListNode(9);
    head1->next->next->next->next->next = commonNode;
    head2->next->next = commonNode;

    std::cout << "链表1：";
    for (ListNode* curr = head1; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    std::cout << "链表2：";
    for (ListNode* curr = head2; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    ListNode* result = findFirstCommonNode(head1, head2);
    if (result) {
        std::cout << "第一个公共节点的值为 " << result->val << std::endl;
    } else {
        std::cout << "没有公共节点。" << std::endl;
    }

    return 0;
}

11、链表相加(二)

11.1、问题描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9 要求：空间复杂度 O(n)，时间复杂度O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

示例1
输入：[9,3,7],[6,3]
返回值：
说明：
如题面解释
示例2
输入：[0],[6,3]
返回值：

11.2、思路及代码

思路：

创建一个虚拟头节点 dummy 作为结果链表的头节点，初始化两个指针 p1 和 p2 分别指向两个输入链表的头节点。
使用变量 carry 保存进位信息，初始值为0。
从链表的尾部（个位）开始，逐位相加两个链表的节点值，并加上进位 carry。
将每一位的结果添加到结果链表中，同时更新进位值 carry。
最后，如果还存在进位，需要额外添加一个节点表示进位。
返回结果链表的头节点。

参考代码：

#include <iostream>

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

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* current = dummy; // 当前节点指针
    int carry = 0; // 进位值

    while (p1 || p2) {
        int x = (p1) ? p1->val : 0;
        int y = (p2) ? p2->val : 0;

        int sum = x + y + carry;
        carry = sum / 10;

        current->next = new ListNode(sum % 10);
        current = current->next;

        if (p1) p1 = p1->next;
        if (p2) p2 = p2->next;
    }

    if (carry > 0) {
        current->next = new ListNode(carry);
    }

    return dummy->next; // 返回结果链表的头节点
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val;
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values1 = {2, 4, 3};
    std::vector<int> values2 = {5, 6, 4};
    ListNode* l1 = createList(values1);
    ListNode* l2 = createList(values2);

    std::cout << "链表1：";
    printList(l1);
    std::cout << "链表2：";
    printList(l2);

    ListNode* result = addTwoNumbers(l1, l2);
    std::cout << "相加结果：";
    printList(result);

    return 0;
}

12、单链表的排序

12.1、问题描述

给定一个节点数为n的无序单链表，对其按升序排序。

示例1
输入：[1,3,2,4,5]
返回值：
示例2
输入：[-1,0,-2]
返回值：

12.2、思路及代码

思路：

使用递归将链表分为两半，直到每个子链表只包含一个节点或为空。
对每一对相邻的子链表进行合并，得到一个新的有序子链表。
重复步骤2，直到合并到最后得到一个完全有序的链表。

参考代码：

#include <iostream>

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

ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head; // 链表为空或只有一个节点时无需排序

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

    // 使用快慢指针找到链表中点
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* left = head;
    ListNode* right = slow->next;
    slow->next = nullptr;

    // 递归排序两个子链表
    left = sortList(left);
    right = sortList(right);

    // 合并排序后的两个子链表
    return merge(left, right);
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val;
        head = head->next;
        if (head) std::cout << " -> ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {4, 2, 1, 3};
    ListNode* head = createList(values);

    std::cout << "原链表：";
    printList(head);

    head = sortList(head);

    std::cout << "排序后的链表：";
    printList(head);

    return 0;
}

13、判断一个链表是否为回文结构

13.1、问题描述

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

示例1
输入：
返回值：true
示例2
输入：
返回值：false
说明：2->1
示例3
输入：
返回值：true
说明：1->2->2->1

13.2、思路及代码

思路：

使用快慢指针找到链表的中点。
将链表的后半部分反转。
比较前半部分和反转后的后半部分是否一致。

参考代码：

#include <iostream>

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

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

// 判断链表是否为回文结构
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) {
        return true; // 空链表或只有一个节点时是回文结构
    }

    // 使用快慢指针找到链表的中点
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 反转链表的后半部分
    ListNode* secondHalf = reverseList(slow->next);
    slow->next = nullptr;

    // 比较前半部分和反转后的后半部分是否一致
    ListNode* p1 = head;
    ListNode* p2 = secondHalf;

    while (p1 && p2) {
        if (p1->val != p2->val) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    return true;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

int main() {
    std::vector<int> values1 = {1, 2, 2, 1};
    ListNode* head1 = createList(values1);

    std::cout << "链表1：";
    for (ListNode* curr = head1; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    bool result1 = isPalindrome(head1);
    if (result1) {
        std::cout << "链表1是回文结构。" << std::endl;
    } else {
        std::cout << "链表1不是回文结构。" << std::endl;
    }

    std::vector<int> values2 = {1, 2, 3, 4};
    ListNode* head2 = createList(values2);

    std::cout << "链表2：";
    for (ListNode* curr = head2; curr != nullptr; curr = curr->next) {
        std::cout << curr->val << " ";
    }
    std::cout << std::endl;

    bool result2 = isPalindrome(head2);
    if (result2) {
        std::cout << "链表2是回文结构。" << std::endl;
    } else {
        std::cout << "链表2不是回文结构。" << std::endl;
    }

    return 0;
}

14、链表的奇偶重排

14.1、问题描述

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

示例1
输入：
返回值：
说明：
1->2->3->4->5->6->NULL
重排后为
1->3->5->2->4->6->NULL
示例2
输入：
返回值：
说明：
1->4->6->3->7->NULL
重排后为
1->6->7->4->3->NULL 奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

14.2、思路及代码

思路：

使用两个指针 odd 和 even 分别指向奇数位和偶数位的起始位置，同时保留 even 的起始位置作为偶数位的头节点。
遍历链表，将奇数位节点和偶数位节点分别串联起来。
最后，将奇数位链表的尾节点连接到偶数位链表的头节点即可。

参考代码：

#include <iostream>

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

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next || !head->next->next) {
        return head; // 链表为空或只有一个或两个节点时无需重排
    }

    ListNode* odd = head;
    ListNode* even = head->next;
    ListNode* evenHead = even; // 偶数位链表的头节点

    while (even && even->next) {
        odd->next = even->next; // 奇数位节点指向下一个奇数位节点
        odd = odd->next;

        even->next = odd->next; // 偶数位节点指向下一个偶数位节点
        even = even->next;
    }

    odd->next = evenHead; // 将奇数位链表的尾节点连接到偶数位链表的头节点

    return head;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val;
        head = head->next;
        if (head) std::cout << " -> ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = createList(values);

    std::cout << "原链表：";
    printList(head);

    head = oddEvenList(head);

    std::cout << "重排后的链表：";
    printList(head);

    return 0;
}

15、删除有序链表中重复的元素

15.1、问题描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次例如：给出的链表为1→1→2,返回1→2. 给出的链表为1→1→2→3→3,返回1→2→3.

示例1
输入：
返回值：
示例2
输入：{}
返回值：{}

15.2、思路及代码

思路：

遍历链表，比较当前节点的值与下一个节点的值是否相等。
如果相等，将当前节点的 next 指针指向下一个节点的下一个节点，跳过重复元素。
如果不相等，继续遍历下一个节点。

参考代码：

#include <iostream>

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

ListNode* deleteDuplicates(ListNode* head) {
    if (!head) {
        return nullptr; // 链表为空，无需处理
    }

    ListNode* current = head;

    while (current && current->next) {
        if (current->val == current->next->val) {
            ListNode* duplicate = current->next;
            current->next = current->next->next;
            delete duplicate; // 释放重复元素的内存
        } else {
            current = current->next;
        }
    }

    return head;
}

// 创建链表的函数
ListNode* createList(std::vector<int>& values) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : values) {
        current->next = new ListNode(val);
        current = current->next;
    }

    return dummy->next;
}

// 打印链表的函数
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val;
        head = head->next;
        if (head) std::cout << " -> ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {1, 1, 2, 3, 3};
    ListNode* head = createList(values);

    std::cout << "原链表：";
    printList(head);

    head = deleteDuplicates(head);

    std::cout << "删除重复元素后的链表：";
    printList(head);

    return 0;
}

微服务

文档

基础

链表 ​

1、反转链表 ​

1.1、问题描述 ​

1.2、思路及代码 ​

2、链表内指定区间反转 ​

2.1、问题描述 ​

2.2、思路及代码 ​

3、 链表中的节点每k个一组翻转 ​

3.1、问题描述 ​

3.2、思路及代码 ​

4、合并两个排序的链表 ​

4.1、问题描述 ​

4.2、思路及代码 ​

5、 合并k个已排序的链表 ​

5.1、问题描述 ​

5.2、思路及代码 ​

6、判断链表中是否有环 ​

6.1、问题描述 ​

6.2、思路及代码 ​

7、链表中环的入口结点 ​

7.1、问题描述 ​

7.2、思路及代码 ​

8、链表中倒数最后k个结点 ​

8.1、问题描述 ​

8.2、思路及代码 ​

9、删除链表的倒数第n个节点 ​

9.1、问题描述 ​

9.2、思路及代码 ​

10、两个链表的第一个公共结点 ​

10.1、问题描述 ​

10.2、思路及代码 ​

11、链表相加(二) ​

11.1、问题描述 ​

11.2、思路及代码 ​

12、单链表的排序 ​

12.1、问题描述 ​

12.2、思路及代码 ​

13、判断一个链表是否为回文结构 ​

13.1、问题描述 ​

13.2、思路及代码 ​

14、链表的奇偶重排 ​

14.1、问题描述 ​

14.2、思路及代码 ​

15、删除有序链表中重复的元素 ​

15.1、问题描述 ​

15.2、思路及代码 ​

链表

1、反转链表

1.1、问题描述

1.2、思路及代码

2、链表内指定区间反转

2.1、问题描述

2.2、思路及代码

3、链表中的节点每k个一组翻转

3.1、问题描述

3.2、思路及代码

4、合并两个排序的链表

4.1、问题描述

4.2、思路及代码

5、合并k个已排序的链表

5.1、问题描述

5.2、思路及代码

6、判断链表中是否有环

6.1、问题描述

6.2、思路及代码

7、链表中环的入口结点

7.1、问题描述

7.2、思路及代码

8、链表中倒数最后k个结点

8.1、问题描述

8.2、思路及代码

9、删除链表的倒数第n个节点

9.1、问题描述

9.2、思路及代码

10、两个链表的第一个公共结点

10.1、问题描述

10.2、思路及代码

11、链表相加(二)

11.1、问题描述

11.2、思路及代码

12、单链表的排序

12.1、问题描述

12.2、思路及代码

13、判断一个链表是否为回文结构

13.1、问题描述

13.2、思路及代码

14、链表的奇偶重排

14.1、问题描述

14.2、思路及代码

15、删除有序链表中重复的元素

15.1、问题描述

15.2、思路及代码