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

文章预览

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

image.png

解题思路：

1. 使用双指针，快指针与慢指针的间隔为n；
2. 涉及到最后要删除慢指针的节点，为了方便，先开辟一个node为pre，pre的next指向head，快慢指针均从pre开始遍历；
3. 先由快指针向前走n步，再快慢指针同时向前走，直到快指针的next指向空；
4. 那么此时慢指针的next即为要删除的节点，此时令 slow.next=slow.next.next 即可。

Python3代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pre = ListNode(0)
        pre.next = head
        slow, fast = pre, pre
        while n>0:
            n-=1
            fast = fast.next
        
        while fast.next:
            slow = slow.next 
            fast = fast.next
        
        slow.next = slow.next.next
        return pre.next

………………………………