[코딩 테스트] 리트코드 19 - Remove Nth Node From End of List(Medium) in Python

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

 

연결 리스트의 head가 주어졌을 때, 연결 리스트의 끝에서 n번째 노드를 삭제하고 연결 리스트의 head를 리턴하세요!

 

Example 1:

(출처 - 리트코드)

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

 

Example 2:

Input: head = [1], n = 1

Output: []

 

 

풀이

나는 문제에서 말하는 소위 "Two-Pass Solution"으로 풀었다.

 

처음에 한 포인터로 연결 리스트를 순회하면서 연결 리스트의 길이 (length) 를 알아내고,

두번째 포인터로 (length - n)노드의 바로 전 노드를 가리켜,

이 노드의 node.next = (length-n) 바로 다음 노드

로 설정해 (length-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:
        endNode = head #포인터 - 연결 리스트의 길이를 구하기 위함
        length = 1
        
        while endNode.next: # 다음 노드가 있을 때까지 순회
            endNode = endNode.next
            length += 1
            
        if length == 1 and n == 1: # 연결 리스트의 길이가 1이고, 지워야 할 노드가 1번이라면
            head.val = ''
            return head # 빈 연결리스트 반환
            
        if length - n == 0: # 이 경우 맨 처음 노드를 지워야 함
            return head.next # 연결 리스트의 두 번째 노드를 HEAD로 반환한다
        
        # corner cases 위에서 처리 후
        # 일반 케이스 - 지울 노드의 전 노드를 두 번째 포인터로 가리킴
        nodeBefore = head
        for _ in range(length - n - 1):
            nodeBefore = nodeBefore.next        
        nodeBefore.next = nodeBefore.next.next
        
        return head

 

문제 Solution과 Discussion을 보면서 배운 점이,

연결 리스트 문제에서 Dummy Node를 사용하면 Corner Cases 해결이 저절로 되는 경우가 많다는 것이다.

아래의 dummy를 사용한 코드를 보자.

 

def removeNthFromEnd(self, head, n):
    dummy = ListNode(0)
    dummy.next = head
    
    firstPtr = secondPtr = dummy
    
    for _ in range(n): # n번째 노드 가리킴
    	firstPtr = firstPtr.next
    
    while firstPtr and firstPtr.next:
    	firstPtr = firstPtr.next # 첫 번째 포인터는 연결 리스트의 끝을 가리킴
        secondPtr = secondPtr.next # 두 번째 포인터는 연결 리스트의 끝에서 n번째 노드를 가리킴
        
    secondPtr.next = secondPtr.next.next # 연결 리스트의 끝에서 n번째 노드의 연결을 x
    
    return dummy.next # 연결 리스트의 Head 가리킴

이 방법은 dummy 노드도 쓰고, 문제에서 말하는 One-Pass Algorithm을 사용한 방법이다.

 

dummy 노드 사용

연결 리스트의 원래 head 앞에 노드를 새로 추가해줌으로써,

head가 지워져야 할 Corner Cases들을 모두 해결해준다.(처음 풀이에서 두 개의 if문을 모두 해결해줌)

 

 

One-Pass Algorithm

처음 풀이가 (1) 한 포인터로 순회 후, (2) 두 번째 포인터로 다시 순회하는 풀이었다면,

이 번 풀이는 (1) 한 포인터와, 그와 (n + 1)만큼의 거리를 두고 따라오는 두 번째 포인터로 한 번에 순회하는 방법이다("One-Pass").

 

사실 Discussion에서 많은 분들이 지적하듯이 "시간복잡도"에 있어 차이는 없다!

Two-Pass든, One-Pass든 

첫 번째 포인터 -> 연결 리스트 길이 (L) 만큼 이동

두 번째 포인터 -> 연결 리스트 길이 - n 만큼 (L - n) 이동

하기 때문이다.

 

시간 복잡도 = O(2L - n) = O(L)

 

다만 어떤 똑똑한 분들이 Discussion에서 말해주셨듯,

연결 리스트의 길이 L이 길면,

첫 번째 포인터가 순회를 다 끝내고 두 번째 포인터가 순회를 하는 과정에서 (Two-Pass)

이전 정보가 캐시 메모리에서 날아가기 때문에 비교적 시간이 더 걸릴 수 있다.

One-Pass라면 "순회"는 한 번에 하면서 두 포인터를 한 번에 움직이기 때문에,

캐시 메모리에 저장된 정보를 참조하면서 연산이 빨리 될 수 있다.

 

=> 이론적으로는 같은 복잡도를 낸다 하더라도, 실제 연산에서는 더 효과적일 수 있다는 얘기이다.

 

 

 

배운 두 가지 키 포인트

1. 연결 리스트 문제에서는 dummy node를 잘 활용하여라!

2. 실제 CPU 연산의 효용성 또한 생각하여라!