欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

LeetCode 19. 删除链表的倒数第N个节点(双指针和递归的妙用)

程序员文章站 2022-05-18 17:42:27
2020年7月25日 周六 天气晴 【不悲叹过去,不荒废现在,不惧怕未来】本文标题解法1. 快慢指针(我去给你探探路~)解法2. 递归(大神,请收下我的膝盖!)参考文献LeetCode 19. 删除链表的倒数第N个节点这道题如果没有要求使用一趟扫描实现,还是比较简单的,先遍历一次确定链表的长度N,然后这道题就转化为了删除链表的第 N - n + 1 个结点。那么如何实现一趟扫描就解决这道题呢,有两种解法:快慢指针和递归。解法1. 快慢指针(我去给你探探路~)快慢指针的思想:开始时慢指针不动,先...

2020年7月25日 周六 天气晴 【不悲叹过去,不荒废现在,不惧怕未来】



题目简介

LeetCode 19. 删除链表的倒数第N个节点
LeetCode 19. 删除链表的倒数第N个节点(双指针和递归的妙用)
这道题如果没有要求使用一趟扫描实现,还是比较简单的,先遍历一次确定链表的长度N,然后这道题就转化为了删除链表的第 N - n + 1 个结点。那么如何实现一趟扫描就解决这道题呢,有两种解法:快慢指针和递归


解法1. 快慢指针(我去给你探探路~)

快慢指针的思想:开始时慢指针不动,先让快指针移动 n 个位置,然后快慢指针同时移动,之后快指针到达链表尾部的时候,慢指针刚好到达第 N - n 个位置,下一个结点就是需要删除的那个结点~

动图如下,来源于 ”程序员吴师兄“ 的 leetcode 题解,十分感谢。
LeetCode 19. 删除链表的倒数第N个节点(双指针和递归的妙用)
理解了其中的思想之后,代码也就呼之欲出了:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        int N = 0, idx = 0;
        ListNode* preHead = new ListNode(-1);
        preHead->next = head;
        ListNode *fast = preHead, *slow = preHead;
        
        // 快指针先移动 n 个位置
        for(int i=0;i<n+1;++i){
            fast = fast->next;
        }
      
        // 快慢指针同时移动,快指针到达链表尾部时,慢指针到达第 N - n 个位置
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }
        
        // 删除倒数第 n 个结点
        slow->next = slow->next->next;
        return preHead->next;
    }
};

解法2. 递归(大神,请收下我的膝盖!)

递归的解法是我在这道题的评论区看到的,刚开始没看明白,看懂之后不禁感叹:真是妙蛙种子吃着妙脆角妙进了米奇妙妙屋 妙到家了!

先附上代码:

class Solution {
public:
    int cnt = 0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        head->next = removeNthFromEnd(head->next,n);
        cnt++;
        if(cnt==n)  return head->next;
        return head;
    }
};

递归函数在回溯时, cnt 从后往前自加,当 cnt == n 时,即回溯到了倒数第 n 个结点,返回这个结点(head)的下一个结点,相当于删除了此结点。


参考文献

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/comments/

本文地址:https://blog.csdn.net/m0_37433111/article/details/107585290