专栏首页IT那个小笔记19 删除链表的倒数第N个节点

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

01

题目信息

题目地址: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:给定的 n 保证是有效的。

进阶:你能尝试使用一趟扫描实现吗?

02

解法一:倒数转正数

很自然的是我只能通过头节点head多次的next,找到要被删除的节点,但我们获取的定位是倒数第几个。直观的就是我们通过总长度减去倒数就是我们的next次数

public ListNode removeNthFromEnd(ListNode head, int n){
    // 1.统计链表长度
    int count = 0;
    ListNode node = head;
    while(node != null){
        count++;
        node = node.next;
    }
    // 重置node
    node = head;
    // 2.找到被删除节点的前一个
    for(int i = 0; i < count - n - 1; i++){
        node = node.next;
    }
    // 3.删除操作
    if(count == n){
        //如果是头节点
        head = head.next;
    }else{
        node.next = node.next.next;
    }
    return head;
}

现在我们是完成了这样一个思路,但有个地方可以做一个调整,也是要养成的一个习惯。对于一个链表如下图:

它是按某种应用逻辑存储的内容,内容都会有操作有修改的时候,因此为了方便操作以及操作的安全性。通常都会在真正存储数据的链头之前加一个节点它的值和内容无关,用这个额外的节点来做真正的链表节点。

我们第三步删除操作之所以这样分开操作就是因为,我们拿到的是删除节点之前的节点因此删除是头结点的话需要单独处理,这下就不需要了。最后我们去返回数据链的头,也就是真正头的next

public ListNode removeNthFromEnd(ListNode head, int n){
    //加一个头结点
    ListNode listHead = new ListNode(0,head);
    // 1.统计链表长度
    int count = 0;
    ListNode node = head;
    while(node != null){
        count++;
        node = node.next;
    }
    // 重置node
    node = listHead;
    // 2.找到被删除节点的前一个(比之前多一次)
    for(int i = 0; i < count - n; i++){
        node = node.next;
    }
    // 3.删除操作
    node.next = node.next.next;
    return listHead.next;
}

时间O(n),空间O(1)

03

解法二:栈

无论是倒序啊还是倒数都可以想到栈这样一个东西,上个解法我们完整遍历一次统计长度,把倒数转为正数再进行正数次数的next取被删除节点的前驱节点,这次一样进行完整遍历都放到我们的栈里面。

之后再进行倒数次数的出栈操作,之后剩下的栈顶即是被删除节点的前驱节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建真头结点
    ListNode listHead = new ListNode(0, head);
    // 创建栈
    Deque<ListNode> stack = new LinkedList<ListNode>();
    // 从真头结点开始存入
    ListNode node = listHead;
    while (node != null) {
        stack.push(node);
        node = node.next;
    }
    // 依次弹出
    for (int i = 0; i < n; i++) {
        stack.pop();
    }
    // 取栈顶即被删节点的前驱节点
    node = stack.peek();
    // 删除操作
    node.next = node.next.next;
    return listHead.next;
}

时间O(n),创建了栈空间O(n)

04

解法三:一次遍历

两个解法都用到了两次遍历,那么我们有没有方法可以在一次遍历中完成呢?

它就是我们处理链表的经典方式快慢指针,我们用两个指针,快指针领先n次(倒数次数),慢指针在起点,同时迭代。当快指针到了终点,那慢指针岂不是到了倒数第n个。fast起点可以取后一格那么slow就能拿到倒数第n个的前一个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode listHead = new ListNode(0, head);
    // 取的是被删除节点的前驱节点,fast初始化多一格
    ListNode fast = head;
    ListNode slow = listHead;
    int i = 0;
    while (fast != null) {
        // fast先移动n,之后在同步移动
        fast = fast.next;
        if(i>=n) slow = slow.next;
        i++;
    }
    // 直到fast遍历完,slow就停在倒数第n个的前个
    slow.next = slow.next.next;
    return listHead.next;
}

时间O(n),空间O(1)

05

总结

三种解法前两种解法比较常规就顺题意推导正着找和反着找,第三种快慢指针是链表比较常用的一种方式。比如有环,追击问题等等。

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    设置两个指针变量,中间隔N-1个元素,当后面的指针遍历完所有元素指向nil时,前面的指针就指向了想要删除的元素

    Michel_Rolle
  • 19. 删除链表的倒数第N个节点

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-...

    lucifer210
  • LeetCode 19. 删除链表的倒数第N个节点

    freesan44
  • Leetcode No.19 删除链表的倒数第N个节点

    由于我们需要找到倒数第 n 个节点,因此我们可以使用两个指针 fast 和 slow同时对链表进行遍历,并且 fast 比 slow 超前 nn 个节点。当 f...

    week
  • Leetcode打卡 | No.19 删除链表的倒数第N个节点

    之前我们说过 C 和 C++ 中的指针是个好东西 ,在解决这类问题很是方便 。然而 python 是没有这个概念的 ,包括链表也是模拟链表的相关操作 。刷题到这...

    小小詹同学
  • LeetCode 19. 删除链表的倒数第N个节点(双指针)

    Michael阿明
  • 画解算法:19. 删除链表的倒数第N个节点

    https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

    灵魂画师牧码
  • ​LeetCode刷题实战19:删除链表的倒数第N个节点

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode 19:删除链表的倒数第N个节点 Remove Nth Node From End of List

    Given a linked list, remove the n-th node from the end of list and return its he...

    爱写bug
  • LeetCode 19:删除链表的倒数第N个节点 Remove Nth Node From End of List

    Given a linked list, remove the n-th node from the end of list and return its he...

    爱写bug
  • 入门级别的面试题——LeetCode题目19:删除链表的倒数第N个节点

    给定一个链表,删除链表的倒数第n个节点,并且返回链表的头结点,题目给定的 n 保证是有效的。你能尝试使用一趟扫描实现吗?

    二环宇少
  • LeetCode-19 删除链表中的倒数第N个节点

    今天我们学习第19题删除链表中的倒数第N个节点,这是一道中等题。这个题属于面试中的高频题,一定要能手写出来。下面我们看看这道题的题目描述。

    用户3470542
  • 19. 删除链表的倒数第 N 个结点

    CaesarChang张旭
  • 删除链表的倒数第N个节点

    宇宙之一粟
  • 删除链表中倒数第n个节点

    一份执着✘
  • LeetCode - 删除链表的倒数第N个节点

    LeetCode第19题,中等难度,很经典的一道链表相关的题目。一个多月以前做的,当时一看就知道怎么写,结果代码总是差了点...

    晓痴
  • 删除链表的倒数n个节点

    采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。

    大忽悠爱学习
  • 删除链表倒数第N个节点,怎么删?

    题目链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

    代码随想录
  • Swift 删除链表的倒数第N个节点 - LeetCode

    构建双指针first与sec,first先走n步,然后一同运动,当first指向表尾,sec指向的next即是倒数第N个节点,删除即可(next指向next的n...

    韦弦zhy

扫码关注云+社区

领取腾讯云代金券