19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

My Answer 1: Accepted (Runtime: 36 ms - 50.46% / Memory Usage: 14.2 MB - 51.61%)

# 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: ListNode, n: int) -> ListNode:
        if head.next is None:
            return None
        
        # head 앞에 임의의 노드 하나 더 추가
        head2 = ListNode(0, head)
        # head2 의 맨 앞을 가리키는 역할
        head3 = head2
        
        while head2:
            temp = head2
            
            for i in range(n):
                temp = temp.next
            
            # 뒤에서 n 번째의 값을 제거
            if temp.next is None:
                head2.next = head2.next.next
                break
            
            head2 = head2.next
        
        return head3.next

맨 앞이 제거되는 경우도 있으므로 head 앞에 임의의 노드를 하나 더 추가한 head2 를 이용
head3 는 head2 의 맨 앞을 가리킨다.

특정 노드에서 다음 노드로 n 번 이동 후(for 문)
그때의 next 값이 None 이면 뒤에서 n 번째라는 의미 => head2.next = head2.next.next 로 제거

임의의 노드를 제외한 head3.next 를 리턴

반복문 2개로 노드마다 n 개의 다음 노드를 확인해서 비효율적일거 같기두..ㅎ

One-Pass

Solution 1: Runtime: 28 ms - 93.12% / Memory Usage: 14.3 MB - 17.95%

# 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: ListNode, n: int) -> ListNode:
        temp = temp2 = head
        
        for i in range(n):
            temp = temp.next
        
        if not temp:  # cases like [1] 2
            return head.next
        
        while temp.next:
            temp = temp.next
            temp2 = temp2.next 
        
        temp2.next = temp2.next.next
      
        return head

깔끔하게 이거 외워야겠다. 원패스