删除链表的倒数第n个节点

删除链表的倒数第n个节点_牛客题霸_牛客网

问题简述

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

思路：快慢指针

• 单向链表指针问题的难点是，不能回退，往往是多走了一个位置或者少走了一个位置；

• 不用记，多试几次或者手工模拟一下；

Python

class Solution:
    def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        
        fast = slow = dummy
        # fast 先走 n 步
        for _ in range(n):
            fast = fast.next
        
        while fast.next:  # 这里为什么是 fast.next？手动模拟一下
            fast = fast.next
            slow = slow.next
        
        # 退出循环时，slow 正好指向需要删除节点的前一个
        slow.next = slow.next.next
        return dummy.next