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

이런 형태로 현재는 prev.next는 3일텐데 4 로 바꾼다는 뜻이다
그러면 2 -> 4를 가르키면서 3은 위치를 찾을 수 없기 때문에 삭제 된다.

하지만 이 방법은 leetcode에서 원하는 방법이 아니다.

문제해결을 위해 runner기법을 알아야 한다.

Runner 기법이란?

SLOW 와 FAST라는 포인터를 두고
SLOW는 한칸씩 이동하고 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를 추가하는 이유기도 한다.