算法练习-删除链表倒数第n个节点(思路+流程图+代码)

发布时间:2024年01月23日

难度参考

????????难度:简单

? ? ? ? 分类:链表

? ? ? ? 难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。

题目

????????给你一个链表,删除链表的倒数第个结点,并且返回链表的头结点。
????????示例1:
????????输入:head=[1,2,3,4,5],n=2
????????输出:[1,2,3,5]
????????额外要求:
????????尝试使用一趟扫描实现?

思路

???????? 额外要求提及需要一次扫描实现,但是需要注意的是单链表是从前向后遍历的。因此,删除倒数第n个节点就是删除正数第len-n个节点这个思路是从往后前遍历的。故不可行。

????????当需要删除链表的倒数第n个节点并返回头结点时,可以使用双指针的方法,通过一趟扫描实现。以下是解题思路:

  1. 使用双指针: 定义两个指针fastslow,初始都指向虚拟头结点(dummy node)。

  2. 移动fast指针:fast指针向前移动n+1步,使得fast指针和slow指针之间相差n个节点。这样,当fast指针到达链表尾部时,slow指针指向要删除节点的前一个节点。

  3. 移动fast和slow指针: 同时移动fastslow指针,直到fast指针指向链表尾部的下一个节点。

  4. 删除倒数第n个节点: 此时,slow指针指向的节点就是要删除的节点的前一个节点。修改slow->next指向slow->next->next,即可删除倒数第n个节点。

  5. 返回头结点: 返回虚拟头结点的next即为修改后的链表的头结点。

示例

????????假设有一个链表 [1, 2, 3, 4, 5],并且要删除倒数第2个节点。

????????初始链表:? ??

1 -> 2 -> 3 -> 4 -> 5

????????初始化指针: 创建虚拟头结点,fastslow指针都指向虚拟头结点。

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
  ^     
slow fast

????????移动fast指针:fast指针向前移动3步(n+1步),达到节点3。

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
  ^                ^  
  slow           fast

????????移动fast和slow指针: 同时移动fastslow指针,直到fast指针到达链表尾部的下一个节点。此时,slow指针指向要删除节点的前一个节点。

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                   ^               ^
                  slow            fast

????????删除倒数第n个节点: 删除节点3。

dummy -> 1 -> 2 -> 4 -> 5 -> null
                   ^          ^
                  slow       fast

????????返回头结点: 返回虚拟头结点的next即为修改后的链表的头结点,即节点

1 -> 2 -> 4 -> 5

????????因此,删除倒数第2个节点后的链表为 [1, 2, 4, 5]

梳理

????????这种删除链表倒数第n个节点的算法的关键在于使用了两个指针(快指针和慢指针),通过它们之间的差距来找到要删除的节点。

????????快慢指针在这个问题中的原理是通过设置两个指针,一个快指针和一个慢指针,它们之间的步长差异为n+1。这种设置使得当快指针达到链表尾部时,慢指针正好指向要删除的节点的前一个节点。

  1. 双指针初始化: 初始时,快指针fast和慢指针slow都指向虚拟头结点。这样,它们之间的距离是0。

  2. 移动快指针: 快指针fast先向前移动n+1步。这是因为我们希望fast指针在慢指针slow之前n个节点,为了处理删除倒数第n个节点的情况。

  3. 同时移动快慢指针: 接下来,我们同时移动快指针fast和慢指针slow,直到fast指针到达链表尾部的下一个节点。由于fastslow之间的初始距离是n+1,当fast到达尾部时,slow正好指向要删除节点的前一个节点。

  4. 删除倒数第n个节点: slow->next就是要删除的节点,我们修改slow->next指向slow->next->next,即可删除倒数第n个节点。

  5. 返回头结点: 返回虚拟头结点的next即为修改后的链表的头结点。

????????这种算法通过使用双指针,避免了对链表的多次遍历,实现了一趟扫描。由于fastslow之间的距离是n+1,当fast到达链表尾部时,slow指向的就是要删除节点的前一个节点。这样就能在一次遍历中找到并删除倒数第n个节点。

代码

#include <iostream>

using namespace std;

// 定义链表节点结构
struct ListNode {
    int val;          // 节点值
    ListNode* next;    // 下一个节点指针
    ListNode(int x) : val(x), next(nullptr) {}
};

// 删除链表的倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 创建一个虚拟头节点,方便处理删除头节点的情况
    ListNode* dummy = new ListNode(0); // 创建虚拟头节点,值为0
    dummy->next = head; // 将虚拟头节点指向传入的头节点
    
    // 初始化快指针和慢指针,都指向虚拟头节点
    ListNode* fast = dummy; // 快指针,用于提前移动n+1步
    ListNode* slow = dummy; // 慢指针,用于定位要删除节点的前一个节点

    // 快指针先向前移动n+1步
    for (int i = 0; i <= n; ++i) {
        fast = fast->next; // 快指针向前移动一步
    }

    // 同时移动快慢指针,直到快指针到达链表尾部的下一个节点
    while (fast != nullptr) {
        fast = fast->next; // 快指针向前移动一步
        slow = slow->next; // 慢指针向前移动一步
    }

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

    return dummy->next; // 返回修改后的链表头
}

// 辅助函数:打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " "; // 输出节点值
        head = head->next;          // 移动到下一个节点
    }
    cout << endl;
}

int main() {
    // 示例用法
    ListNode* head = new ListNode(1); // 创建头节点,值为1
    head->next = new ListNode(2); // 创建第二个节点,值为2
    head->next->next = new ListNode(3); // 创建第三个节点,值为3
    head->next->next->next = new ListNode(4); // 创建第四个节点,值为4
    head->next->next->next->next = new ListNode(5); // 创建第五个节点,值为5

    int n = 2;
    ListNode* result = removeNthFromEnd(head, n); // 调用删除倒数第n个节点的函数

    cout << "修改后的链表: ";
    printList(result); // 打印修改后的链表

    return 0;
}

????????时间复杂度:O(n)
????????空间复杂度:O(1)

打卡

文章来源:https://blog.csdn.net/qq_54813250/article/details/135786569
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。