C++进阶练习删除链表的倒数第N个结点详解

目录
  • 1.链接
  • 2.题目描述
  • 3.解题思路
  • 4.题解

1.链接

19. 删除链表的倒数第 N 个结点.

2.题目描述

3.解题思路

方法一

1.在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

例如，在本题中，如果我们要删除节点 y，我们需要知道节点 y 的前驱节点 x，并将 x 的指针指向 y 的后继节点。

但由于头节点不存在前驱节点，因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。特别地，在某些语言中，由于需要自行对内存进行管理。因此在实际的面试中，对于「是否需要释放被删除节点对应的空间」这一问题，我们需要和面试官进行积极的沟通以达成一致。下面的代码中默认不释放空间。

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

方法二

我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

设置虚拟节点 dummyHead 指向 head

设定双指针 p 和 q，初始都指向虚拟节点 dummyHead

移动 q，直到 p 与 q 之间相隔的元素个数为 n

同时移动 p 与 q，直到 q 指向的为 NULL

将 p 的下一个节点指向下下个节点

4.题解

方法一

/**
 * 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:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

方法二

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }
        while(q){
            p = p->next;
            q = q->next;
        }
        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;
        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
    }
};

到此这篇关于C++进阶练习删除链表的倒数第N个结点详解的文章就介绍到这了,更多相关C++删除链表节点内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现单链表删除倒数第k个节点的方法

    本文实例讲述了C++实现单链表删除倒数第k个节点的方法.分享给大家供大家参考,具体如下: 题目: 删除单链表中倒数第k个节点 解题思路及算法代码: 标尺法,定义两个指针指向链表头结点,先让一个走k步,然后两个指针同时开始走,当先走的指针走到末尾时,后走的指针指向的结点就是需要删除的结点. 单链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 删除倒数第K结点操作代码: //head表示头结

  • 基于Python和C++实现删除链表的节点

    给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点. 返回删除后的链表的头节点. 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 ->

  • C++删除链表中间节点的方法

    本文实例讲述了C++删除链表中间节点的方法.分享给大家供大家参考,具体如下: 题目: 给定链表头结点head,实现删除链表的中间节点函数. 解题思路及代码: 快慢指针,快指针走两步,慢指针一步. 当快指针走到终点时,慢指针正好是链表中间节点,删除此节点即可. 链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 算法C++代码: Node* removeMidNode(pLinkedList

  • C++链表节点的添加和删除介绍

    目录 前言 1. 节点的创建 2. 链表的定义 3. 创建节点 4. 节点的插入 4.1 头插法 4.2 尾插法 4.3 插入中间节点 总结 前言 链表是一种动态的数据结构,因为在创建链表时,不需要知道链表的长度,只需要对指针进行操作. 1. 节点的创建 链表的节点包括两部分,分别是:数据域和(指向下一个节点的)指针域. struct Node { int data; struct Node* next; }; 2. 链表的定义 struct Node* createList() { //创建一

  • 剑指offer之C++语言实现链表(两种删除节点方式)

    1 问题 用C++语言实现链表 2 代码实现 #include <iostream> #include <stdlib.h> using namespace std; class List { public: List(); ~List(); List* createNode(int value);//创建节点 bool insertNode(List *node);//插入节点 void printList();//打印节点 bool deleteNode(List *node)

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • C++进阶练习删除链表的倒数第N个结点详解

    C++进阶练习删除链表的倒数第N个结点详解

    目录 1.链接 2.题目描述 3.解题思路 4.题解 1.链接 19. 删除链表的倒数第 N 个结点. 2.题目描述 3.解题思路 方法一 1.在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的 next指针指向链表的头节点.这样一来,我们就不需要对头节点进行特殊的判断了. 例如,在本题中,如果我们要删除节点 y,我们需要知道节点 y 的前驱节点 x,并将 x 的指针指向 y 的后继节点. 但由于头节点不存在前驱节点,因此我们需要在删除头节点时进行特殊判断.但如果我

  • 如何利用Java输出链表中倒数第k个结点

    如何利用Java输出链表中倒数第k个结点

    目录 前言 问题描述 方法一 方法描述 动画演示 代码如下 方法二 方法描述 动画演示 代码如下 总结 前言 链表是一种数据结构,和数组同级.比如,Java中我们使用的ArrayList,其实现原理是数组.而LinkedList的实现原理就是链表了.链表在进行循环遍历时效率不高,但是插入和删除时优势明显 本文主要介绍的是输出链表中倒数第k个结点,下面来一起看看详细的介绍吧 问题描述 给你一个单链表,输出倒数第k个结点,如下图链表中,输出倒数第k个结点,比如 k = 2,输出5这个结点. 方法一

  • Oracle删除表及查看表空间的实例详解

    Oracle常用的基本命令 --1.用户下表中注释模糊查询: 例如查询与优惠券关联的表 SELECT * FROM user_tab_comments t WHERE t.comments LIKE '%优惠券%'; ![这里写图片描述](http://img.blog.csdn.net/20170321112728053?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDQyNzkzNQ==/font/5a6L5L2T/fontsize/40

  • Spring boot jpa 删除数据和事务管理的问题实例详解

    今天我们介绍的是jpa删除和事务的一些坑,接下来看看具体内容. 业务场景(这是一个在线考试系统)和代码:根据问题的id删除答案 repository层: int deleteByQuestionId(Integer questionId); service 层: public void deleteChoiceAnswerByQuestionId(Integer questionId) { choiceAnswerRepository.deleteByQuestionId(questionId)

  • Java 添加、删除、格式化Word中的图片步骤详解( 基于Spire.Cloud.SDK for Java )

    本文介绍使用Spire.Cloud.SDK for Java提供的ImagesApi接口来操作Word中的图片.具体可通过addImage()方法添加图片.deleteImage()方法删除图片.updateImageFormat()格式化Word中的图片以及getImageFormat()获取Word中的图片格式等.操作方法和代码示例可参考下文中的步骤. 步骤1:导入jar文件 创建Maven项目程序,通过maven仓库下载导入.以IDEA为例,新建Maven项目,在pom.xml文件中配置m

  • 删除 Tomcat webapps 目录自带项目方式详解

    目录 1.webapps目录中的项目 2.修改配置文件 1.webapps目录中的项目 本文将 %CATALINA_HOME% 目录称为“tomcat”目录. 在 Tomcat 8.0 的 tomcat/webapps 目录中,含有 5 个 Tomcat 自带的 Web 项目,如下所示: docs有关于 Tomcat 的介绍和操作文档等examples小程序示例:如 websocket 等host-manager进行 Host 管理manager进行 Server Status 和 Applic

  • Python单向链表和双向链表原理与用法实例详解

    Python单向链表和双向链表原理与用法实例详解

    本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下

  • java实现单链表增删改查的实例代码详解

    package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l

  • python链表的基础概念和基础用法详解

    python链表的基础概念和基础用法详解

    本文为大家分享了python链表的基础概念和基础用法,供大家参考,具体内容如下 一.什么是链表 链表是由多个不同的节点组成,每个节点通过指针区域关联到一起链表的头指针,指向了头节点,通过头指针可以找到其他节点信息 二.什么是节点 链表由节点组成,每个节点又包含两个部分,一个是元素区域,一个是指针区域.元素区域存储的是,当前节点的数值,指针区域指向下一个节点的对象.在C语言中,指针应该是指向下一个元素的的内存地址,因python中不研究指针,这里用下一个节点的对象代替.这样我们就能通过指针区域,找

  • java实现单链表中是否有环的方法详解

    这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇

随机推荐