力扣之链表1—19. 删除链表的倒数第N个节点

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

示例：

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

当删除了倒数第二个节点后，链表变为 1->2->3->5.
方法一：
首先计算链表长度lens，然后遍历找到他的第lens–n个节点，进行删除节点操作

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        if head == None or n == 0:
            return head
        lens=0
        cur = head
        pre = None
        while cur:
            lens+=1
            cur = cur.next
        if lens == n:
            return head.next
        pos=0
        cur = head
        while pos < lens - n:
            pre = cur
            cur = cur.next
            pos += 1
        pre.next = cur.next
        return head

l1 = ListNode(1)
l1.next = l11 = ListNode(2)
l11.next = l12 = ListNode(3)
l12.next = l13 = ListNode(4)
s = Solution()
num = s.removeNthFromEnd(l1,3)
while num:
    print(num.val,end="")
    num = num.next

方法2
使用双指针的方法，第一个指针从列表的开头向前移动 n+1步，而第二个指针将从列表的开头出发。当第一个指针移到链表尾部，此时第二个指针将指向从最后一个结点数起的第 n+1 个结点

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        if head == None or n == 0:
            return head
        cur = head
        while n > 0 and cur:
            cur = cur.next
            n -= 1
        #说明n = lens
        if n==0 and cur == None:
            return head.next
        # 说明n>链表长度
        if n >=0 and cur == None:
            return head
        slow = head
        while cur.next:
            slow = slow.next
            cur = cur.next
        slow.next = slow.next.next
        return head

l1 = ListNode(1)
l1.next = l11 = ListNode(2)
l11.next = l12 = ListNode(3)
l12.next = l13 = ListNode(4)
s = Solution()
num = s.removeNthFromEnd(l1,1)
while num:
    print(num.val,end="")
    num = num.next