[Leetcode] 19. Remove Nth Node From End of List

문제 바로가기

Time Complexity: O(n)
Space Complexity: O(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: ListNode, n: int) -> ListNode:
        headNode = ListNode(next=head)
        node = headNode
        stack = list()
        while node:
            stack.append(node)
            node = node.next
        
        numStack = len(stack)
        parentNode = stack[numStack - n - 1]
        node = stack[numStack - n]
        parentNode.next = node.next
        
        return headNode.next

선 정찰형(?) 풀이

Time Complexity: O(n)
Space Complexity: O(1)

# 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:
        # 선발대가 후발대보다 n 노드 앞서갈 때, 선발대가 끝에 도달하면
        # 선발대와 후발대의 간격은 n노드이므로 후발대의 위치는 끝에서 n번째 노드가 될 것이다.
        headNode = ListNode(next=head)
        firstNode = headNode
        secondNode = headNode
        
        for i in range(n):
            firstNode = firstNode.next
        
        # 후발대의 위치가 끝에서 n+1번째 노드에 도달할 때까지 반복
        while firstNode.next:
            firstNode = firstNode.next
            secondNode = secondNode.next
        
        secondNode.next = secondNode.next.next

        return headNode.next