•
문제 설명 : 주어진 연결리스트 Head를 사용하여, 연결리스트의 뒤에서 n번째 노드를 삭제 처리한다.
•
풀이 방법
◦
경우의 수는 4가지이다.
▪
head만 존재하는 연결리스트일 때
▪
삭제 대상 노드가 맨 왼쪽일 때
▪
삭제 대상 노드가 맨 오른쪽일 때
▪
삭제 대상 노드가 중간 노드일 때
◦
투포인터를 사용하여, 삭제 대상 노드를 찾는다.
▪
left와 right를 n만큼 간격을 설정한 후, right를 끝까지 이동시키면 left는 자연스럽게 뒤에서 n번째 노드가 된다.
▪
이는 중간 노드를 구할 때, slow / fast를 사용하는 방식과 동일하다.
◦
주의할점은 “맨 왼쪽 노드 삭제” 일때와 “중간 노드 삭제” 의 경우, 둘 다 left가 head일 수 있다는 점이다.
▪
예시로, [1,2,3] / n = 1 이라면 중간노드 삭제
▪
[1,2,3] / n = 2 이라면 맨 왼쪽노드 삭제
▪
하지만, 둘다 left가 head인 건 동일하다. 즉 다른 조건을 추가하여 구분해야한다.
•
이를 위해, 실제 연결 리스트의 길이와 n의 길이가 동일한지 확인하였다.
•
시간복잡도 :
•
성공 코드
# Definition for singly-linked list.
# 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]:
left, right = head, head
list_len = 1
# 하나의 node만 있는 경우
if head.next == None:
return None
# n만큼 right 이동
for _ in range(n):
if right.next:
right = right.next
list_len += 1
# right를 끝까지 보내는동안 left 함께 이동
# left는 뒤에서 n + 1번째 위치로 오게된다. -> left.next가 삭제 대상
while right and right.next != None:
left = left.next
right = right.next
list_len += 1
# 가장 오른쪽 삭제하는 경우
if n == 1:
left.next = None
# 삭제 대상이 맨 왼쪽인 경우
elif left == head and list_len == n:
head = head.next
# 중간 값을 삭제하는 경우
else:
left.next = left.next.next
return head
Python
복사