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

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

解题思路

解法一

1. 遍历链表，求出链表长度k

2. 第二次遍历，根据总长度k - n，得出要删除的节点的前一个节点x

3. 然后将x节点next指针指向x的下下一个节点，就可以删除节点了

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head or n < 0:
            return head
        p = ListNode(-1)
        p.next,a,b,k = head,p,p,0
        while a.next:
            a,k = a.next,k+1
        if k < n:
            return head
        num = k - n
        while num:
            b, num = b.next,num -1
        b.next = b.next.next
        return p.next
            

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = ListNode(-1)
        p.next,a,b = head,p,p
        while n > 0 and b:
            b,n = b.next,n-1
        if not b:
            return head
        while b.next:
            a,b = a.next,b.next
        a.next = a.next.next
        return p.next

解题二

使用双指针法，链表长度为k，首先找到第k-n节点i，将i的next指针指向下下一个节点即可

1. 设指针a,b
2. b指针先走n步
3. a，b指针同时往前走，当b指针走到链表末尾时，a指针就正好走到要删除的节点的前一个位置，最后a节点的next指针指向下下一个节点，就完成删除操作

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = ListNode(-1)
        p.next,a,b = head,p,p
        while n > 0 and b:
            b,n = b.next,n-1
        if not b:
            return head
        while b.next:
            a,b = a.next,b.next
        a.next = a.next.next
        return p.next