leetcode 19題解翻訳Python版

19. Remove Nth Node From End of List
タイトルの説明:
Given a linked list, remove the nth node from the end of list and return its head.
Example 1:

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: 1. Given n will always be valid. 2. Try to do this in one pass.
タイトル翻訳
順序付けされたチェーンテーブルが与えられ、後から前数のn番目のノードが削除され、削除されたチェーンテーブルヘッダポインタが返される.
例1:

     ：1->2->3->4->5，n = 2
     2       ：1->2->3->5

注意:1.与えられたチェーンテーブルは常に正しい.1回のループで操作を完了
解題案
ラベル:Linked List
考え方:

本題では、2つのポインタ、pre、endを維持する必要があります.初期化が開始されると、preポインタはチェーンヘッダノードを指し、endポインタはpre+nのノード位置を指す.次にpreとendポインタの位置を同時に後方に移動して、endポインタが最後のノードを指すようにし、preポインタがend-nのノード位置(すなわち、最後からn番目の要素の前のノード)を指すと、それを削除する.

チェーンテーブル長がnの場合,アルゴリズム複雑度O(n)である.

コード:

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


class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        pre = head
        end = head
        for _ in range(n):
            end = end.next
        if end is None:  #               ，               
            return head.next
        while end.next is not None:
            pre = pre.next
            end = end.next
        pre.next = pre.next.next 
        return head