LeetCode19. 删除链表的倒数第N个节点_删除链表的倒数第n个节点 python

题目大意：删除一个单链表中的倒数第N个结点

题目分析：首先，获得单链表中的结点个数count，然后从前往后找到第count-N+1个结点，即我们要删除的结点，删除即可。时间复杂度：两次遍历单链表即可。

代码展示：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def removeNthFromEnd(self, head, n):
        temp = head
        count = 0
        while temp!=None:
            temp = temp.next
            count += 1
        temp = head
        index = 0
        if count==n:
            return head.next
        else:
            while index!=(count-n-1):
                temp = temp.next
                index += 1
            temp.next = temp.next.next
            return head

方法二：时间复杂度：一次遍历单链表即可。 首先，用两个指针p,q分别指向头结点，然后先将其中一个指针p向后移动N个位置，再将p,q同时往后移动，当指针p移动到末尾时，q指针指向的结点即为我们要删除的结点。

代码展示：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def removeNthFromEnd(self, head, n):
        p = head
        q = head
        index = 0
        while index!= n:
            p = p.next
            index += 1 
        if p==None:
            return head.next
        while p.next!= None:
            p = p.next
            q = q.next
        q.next = q.next.next
        return head