174. 删除链表中倒数第n个节点双指针

给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。 样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

**166. 链表倒数第n个节点 **也是这个思路。

双指针

从后往前删除第n个节点,如果是数组,那么可以从后往前找到第n个然后删除就行了,双向指针也可这么做,双向链表的话也可以从后往前,但是单向链表要注意的是只能从前向后遍历,一旦越过这个节点,就找不到了(除非从头再来)。 单向链表经常使用假节点来指向头节点,可以降低变成的复杂度。 我们用两个指针,分别记作del和head,其中del->next=head然后把head向后移动n个位置,这个时候del和head之间相差n+1个位置,然后再把两根指针同时向后移动,直到head指向空指针,这个时候del刚好指向要删除节点的前一个节点(这是必要的,del不能指向要删除的节点,因为链表的删除是必须前一个节点的),这个时候删除这个节点就行了。 有些细节需要注意,画个图就很清楚了:

算法示意

这个我是删除倒数第2个,就是个意思。

ListNode * removeNthFromEnd(ListNode * head, int n) {
        ListNode *first=new ListNode(0);   //定义一个新假节点
        first->next=head;        //这个节点指向链表头
        
        ListNode *del=first;     //一个指针指向这个假节点
        
        for(int i=0;i<n;i++)
        {
            head=head->next;        //先把head向后移动n个位置,这样del和head相差n个位置
        }
        while(head!=NULL)     //然后两根指针同时移动到最后,这样del的下一个节点就是要删除的了
        {
            head=head->next;
            del=del->next;
        }
        del->next=del->next->next;         //删除节点
        return first->next;
        // write your code here
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Delete Node in a Linked List

LeetCode上第237号问题:Delete Node in a Linked List

1082
来自专栏IT可乐

Java数据结构和算法(十三)——哈希表

  Hash表也称散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。它基于数组,通过把关键字映射到数组...

3068
来自专栏数据科学与人工智能

【Python环境】Python函数式编程指南(2):函数

2. 从函数开始 2.1. 定义一个函数 如下定义了一个求和函数: def add(x, y): return x + y 关于参数和返回值的语法细节可以参考...

2205
来自专栏我是攻城师

Java里面关于数组拷贝的几种方式

3074
来自专栏C/C++基础

二路归并排序简介及其并行化

归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若...

1241
来自专栏python学习指南

python字典

本篇将介绍Python里面的字典,更多内容请参考:Python学习指南 Python是什么? Python内置了字典dict的支持,dict全称dicti...

3828
来自专栏java初学

5.1 类、超类和子类

4179
来自专栏aCloudDeveloper

Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

题目:Sort List Sort a linked list in O(n log n) time using constant space complexi...

2296
来自专栏Angular&服务

angular2关于内置通道的使用

minIntegerDigits是要使用的最小数字的整数数字。 默认为1 minFractionDigits是分数后的最小位数。 默认为0 maxFra...

832
来自专栏从流域到海域

《笨办法学Python》 第38课手记

《笨办法学Python》 第38课手记 注意这是第三版的《笨办法学Python》的内容,我后来发现第三版存在很大的问题,就放弃了第三版开始使用第四版,第四版的第...

3418

扫码关注云+社区

领取腾讯云代金券