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

超、凢脫俗 2022-03-25 08:10 155阅读 0赞

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

**示例：**

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

**说明：**

给定的 *n* 保证是有效的。

**进阶：**

你能尝试使用一趟扫描实现吗？

--------------------

思路：

这题做出了不难，难的是要只扫描一遍就做出了。方法是双指针，一个快指针，一个慢指针，初始化这两个指针使得他们距离为n，然后开始往后遍历，当快指针到达链表末端的时候，慢指针刚好在倒数第n-1个位置上，我们就可以操作了。在for循环n次，让fast往后挪n个位子，就可以让slow和fast的距离为n。

这里分两种情况讨论：

1）n = 链表长度，也就是删除第一个结点，那么for循环之后，fast.next为空，此时返回head.next即可。

2）n 不等于 链表长度。先让fast遍历到末端，slow刚好在倒数第 n-1 个位子上，修改一下slow即可。

代码：

--------------------

class Solution(object):  
    def removeNthFromEnd(self, head, n):  
        """  
        :type head: ListNode  
        :type n: int  
        :rtype: ListNode  
        """  
        fast = slow = head  
        for i in range(n):  
            fast = fast.next  
        if not fast:  
            return head.next  
        while fast.next:  
            fast = fast.next  
            slow = slow.next  
        print fast.val,slow.val  
        slow.next = slow.next.next  
        return head

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode.19. 删除链表的倒数第N个节点

19. 删除链表的倒数第N个节点计算链表长度先求出长度，再找到要删除的那个节点的前一个节点。 ![在这里插入图片描述][20201018095432817.

ゝ一世哀愁。/ 2022年12月15日 14:29/ 0 赞/ 147 阅读

相关 LeetCode19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除

女爷i/ 2022年05月16日 02:53/ 0 赞/ 183 阅读

相关【LeetCode】19. 删除链表的倒数第N个节点

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

逃离我推掉我的手/ 2022年05月11日 11:16/ 0 赞/ 171 阅读

相关 LeetCode-19 删除链表的倒数第N个节点

文章目录题目描述我的解法反思优化再次反思

痛定思痛。/ 2022年04月23日 11:50/ 0 赞/ 156 阅读

相关 Leetcode 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除

超、凢脫俗/ 2022年03月25日 08:10/ 0 赞/ 156 阅读

相关 leetcode:19.删除链表的倒数第N个节点

题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2.

Dear 丶/ 2022年02月25日 12:26/ 0 赞/ 195 阅读

相关 LeetCode 19. 删除链表的倒数第N个节点

github：[https://github.com/Renhongqiang/LeetCode][https_github.com_Renhongqiang_LeetCode

亦凉/ 2022年02月16日 13:21/ 0 赞/ 191 阅读

相关 LeetCode(删除链表的倒数第N个节点)

题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2.

野性酷女/ 2022年02月02日 22:53/ 0 赞/ 203 阅读

相关【LeetCode】删除链表的倒数第N个节点

Java code class Solution { public ListNode removeNthFromEnd(List

向右看齐/ 2021年11月11日 15:48/ 0 赞/ 226 阅读

相关 LeetCode删除链表的倒数第N个节点——C

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

比眉伴天荒/ 2021年10月30日 07:44/ 0 赞/ 246 阅读