[2024] 3/3 Leetcode Daily Challenge 19. Remove Nth Node From End of List

19. Remove Nth Node From End of List

예외 처리 방법 1 : if문으로 처리

코드

풀이

step 1: fast pointer만 n만큼 이동

for i in range(n):
	fast = fast.next

step 2: 예외 처리

Input

head = [1]
n = 1

다음과 같은 input이 주어질 경우 step 1의 과정을 거쳤을 때 다음 노드가 존재하지 않으므로 null을 가르킨다.
이후 로직에서 null의 next 값을 호출하므로 문법 오류 발생하게 된다.
이런 경우 head.next 값을 return 해주면 예외처리가 된다.
다음 노드 값이 없기 때문에 빈 배열 [] 이 return 된다.

 if not fast:
            return head.next

step 3: fast pointer를 노드 끝까지 이동
slow pointer가 n만큼의 gap을 두고 동시에 이동

while fast.next:
	slow = slow.next
	fast = fast.next

step 4: slow pointer가 위치한 노드의 다음 노드를 제외해야 한다.
다음 노드를 이어주지 않고 한 칸 건너뛴 뒤 그 다음 노드를 이어준다.

slow.next = slow.next.next

예외 처리 방법 2 : dummyNode 생성

코드

풀이

step 1 : 더미 노드를 생성한다.
dummy = ListNode(0)로 [0] 을 생성한 후 그 다음 노드 값으로 head를 이어준다.

dummy = ListNode(0)
dummy.next = head

step 2: fast pointer만 n만큼 이동

for i in range(n):
	fast = fast.next

step 3: fast pointer를 노드 끝까지 이동
slow pointer가 n만큼의 gap을 두고 동시에 이동

while fast.next:
	slow = slow.next
	fast = fast.next

step 4: slow pointer가 위치한 노드의 다음 노드를 제외해야 한다.
다음 노드를 이어주지 않고 한 칸 건너뛴 뒤 그 다음 노드를 이어준다.

slow.next = slow.next.next

step 5: dummyNode에 처음 생성해줬던 0이 들어있으므로, return 시 그 다음 노드값부터 출력하도록 한다.

return dummy.next

자료 구조

• 연결리스트(Linked List)
  
  구조: value(값), next(다음 노드의 주소)
  참고 영상

알고리즘

• 투포인터 (Two Pointers)
  참고글

시간 복잡도

O(n)