[LeetCode] 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.

 

주어진 Linked list의 끝에서 N번째 있는 노드를 삭제한 리스트를 반환하는 문제

풀이

Linked list는 배열과 달리 특정 위치의 노드로 접근하기 위해서는 head부터 순차적으로 선회해서 접근해야한다. 그렇기 때문에 끝에서 N번째에 자리한 노드의 위치를 파악 하기 위해서는 두 개의 포인터를 활용하여 계산해 주어야한다. 

var dummy = new ListNode(0);
dummy.next = head; 

var fast = dummy;
var slow = dummy;

 

- 노드의 끝에 먼저 도달할 FAST 포인터와 

- FAST에서 N만큼 뒤에 있는 SLOW 포인터

while(n > 0) {
	fast = fast.next;
	n--;
}

 

위 방법으로 두 포인터의 사이를 벌려두면

N = 2인 경우

 

이제 FAST가 마지막 노드에 도달할 때까지 두 포인터를 앞으로 이동해주면 된다.

 

while(fast.next !== null){
	fast = fast.next;
    slow = slow.next;
}

 

N이 2일 떼 FAST 포인터가 마지막에 도달하면 다음과 같은 위치에서 멈출 것이다. 

 

FAST와 SLOW 사이에 있는 값이자 뒤에서 2번째 있는 값인 3과의 연결을 끊어준다. 

slow.next = slow.next.next;

 

이제 앞서 만든 값의 dummy 부분 뒤로 return 해주면 해결

 

답안

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0);
    dummy.next = head;
    
    var fast = dummy;
    var slow = dummy;
    
    while(n > 0) {
        fast = fast.next;
        n--;
    }
    
    while(fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    slow.next = slow.next.next;
    
    return dummy.next;
    
};

 

시간/공간 복잡도

- 시간 복잡도 : O(n)

위 알고리즘은 LinkedList를 두 번 순회한다(traversing).

 

1. FAST 포인터의 이동

FAST 포인터를 SLOW 포인터보다 N개 앞으로 이동시키면서 시간 복잡도 O(n)이 발생하며 여기서 n은 연결된 노드의 수다. 

 

2. N번째 노드 제거 

두번째 while문에서 FAST와 SLOW 모두 fast.next가 NULL이 될 때까지 이동하기 때문에 여기서 발생하는 시간 복잡도는 O(n).마찬가지로 n은 연결된 목록의 노드 수 이다. 

 

- 공간복잡도 : O(1)

LinkedList의 사이즈와 상관없이 일정한 크기의 공간을 차지한다 .

위 알고리즘에서 초기에 생성한 dummy로 인해 단일 더미 노드가 생성되며 이 후 생성된 두 개의 포인터는 공간 복잡도에 영향을 주지 않기 때문에  공간 복잡도는 O(1)이 된다.