58-チェーンテーブルの最後からN番目のノード-leetCode 19(python)を削除

タイトル説明

チェーンテーブルが与えられ、チェーンテーブルの最後からn番目のノードが削除され、チェーンテーブルのヘッダノードが返される.

例

      : 1->2->3->4->5,   n = 2.

            ，     1->2->3->5.

説明:
与えられたn保証は有効である.
ステップ:
スキャンを使って実現してみてもいいですか?

解決構想一

公式問題解の第2の考え方.まずダミーノードを使用して、特殊な状況(チェーンテーブルに1つのノードしかないか、ヘッダノードを削除する必要がある)を簡略化するために、この2つの場合、ダミーノードがなければ、戻り値は空です.次に2つのポインタfastとslowを使用し、fastポインタはn+1ステップ前進し、slow間隔nとなる.その後fastとslowは同時に後方に移動し、fastポインタが最後のノードnullを指すまで、slowが指すノードは削除するノードであり、最後から最初のノードから数番目のn番目のノードであり、slowが次のノードを指すようにすれば、要求されたノードを正常に削除することができます.

コード1

# 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:
        #     
        #                        
        front = ListNode(0)
        front.next,fast,slow = head,front,front
        
        while(n or fast):
            
            if n:
                #        n 
                fast,n=fast.next,n-1
            else:
                #            ，            NULL
                #  slow              
                fast = fast.next
                if fast:
                    slow = slow.next
        slow.next = slow.next.next
        #        
        return front.next

解決構想二

まずチェーンテーブルを遍歴し、チェーンテーブルの長さlengthを得ると、削除するノードの位置はlength-n(0からカウント)であることがわかる.次に、削除するノードの前のノード(位置時にlength-n-1)までチェーンテーブルを再度巡回すると、ノードを削除できます.最終的に戻るのは、ノードを削除したチェーンテーブルです.ここで考慮する特殊な状況は、削除するノードがヘッダノードであれば、length-nは0であり、2回目の巡回時にlength-n-1は取れず、削除できません.だから別の議論をしなければなりません.

コード2

# 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:
        length = 0  #    
        p = head     #    
        
        while p:
            p = p.next
            length += 1
        
        idx = length - n      #        ( 0   )
        p = head              #        
        
        if idx == 0:            #            
            return head.next
        
        for i in range(length):
            
            if i == idx-1:           #             
                p.next = p.next.next
                return head
            else:
                p = p.next             #        ，