リスト問題を解析する「Remove Nth Node From End of List」

leetcodeは接続リストの問題でListNodeとして入力します.
nは、後からいくつかの要素を削除することを示す.

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

まず私の方法でリンクリストを実現しました

独自の方法で接続リストを実装

# 노드 생성
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 연결 리스트 생성
class linkedList:
    def __init__(self):
        self.head = None  # 포인터
        self.size = 0  # 크기 
    #제일 뒤에 추가하는 함수
    def append(self, val):
        if not self.head:  # 헤더가 없으면 헤더에 추가
            self.head = Node(val)
            self.size += 1
            return

        node = self.head  # node 변수에 담아서 고정시켜야지 아래 while문이 작동함 즉 헤더는 고정하고 변수에 담긴 self.head는 이동시키고 추가

        while node.next:  # head의 next가 None일때까지 돌면서 데이터 추가                       
            node = node.next  # node에 node.next로 바꿔주면서 추가
        node.next = Node(val)
        self.size += 1
        
    #뒤에서 삭제하는 함수
    def back_delete(self, idx):              
        real_idx = abs(self.size - idx)     #삭제할 위치 0 부터 찾기위해 뺴줌
        node = self.head                    #현재노드
        prev = self.head                    #prev현재 노드의 전
        for i in range(real_idx):           #real_idx
            prev = node                     #현재 노드를 prev에 저장하고
            node = node.next                #현재 노드의 next를 노드로 지정
            

        prev.next = node.next               #prev.next가 node.next로 가면 node의 연결이 끊겨서 node가 삭제됌
        self.size -= 1

削除ロジックが理解できない人のために再説明するなら
prev.next = node.next
  2    ->   3   ->  4
prev -> node -> node.next
この形で今はprevnextは3番で、4に変えるという意味です.
そうすると、2->4のとき、3は場所が見つからず削除されます.
しかし、これはleetcodeが望んでいる方法ではありません.
問題を解決するためには、ランニングのテクニックを理解しなければならない.

Runnerテクノロジーとは?

SLOWとFASTへ
1コマごとに移動してFASTとSLOWが2倍以上違うように移動するとFASTが末尾に達するとSLOWは真ん中に位置し,そこから探索を開始すると時間が減少する.

Runnerテクノロジーの説明

# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)  #dummy를 만드는 이유는 head부터 시작해도 되지만 여러 예외처리를 해줘야해서이다.
        fast = dummy
        slow = dummy
        head = dummy

        for i in range(n):
            fast = fast.next    #n만큼 fast를 먼저 이동시켜준다.
                                #왜냐하면 우리는 뒤에서부터 삭제하기위해 먼저 가있고 하나씩 가면서 fast.next가 None일때  slow가 삭제할 노드전에 위치한다.
                                #삭제할 노드에 위치하게 짠다면 우리는 prev값을 들고 가지고있어야 노드를 연결한다.

        while fast.next:        #fast.next가 None일때 까지
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next #slow가 현재 prev라고 생각하면 편하다.
        return head.next        #head가 현재 dummy에 위치했으니깐 head.next head로하고 
                                # = dummy를 삭제해도 될거 같은데 [1] 일때를 빼주지 못한다. 
                                #그래서 dummy를 추가하는 이유기도 한다.