CTCI | 중간 노드 삭제

 

Cracking the Coding Interview

Linked List에서 중간 노드 하나를 삭제해라

중간노드를 삭제하는 방법은 여러가지가 있다. 먼저 중간값을 구해야 하는데, 어떻게 중간 노드를 파악할 수 있을까? 먼저, 가장 간단한 로직은, 처음부터 끝까지 한번 travel을 한 후, 노드 갯수를 count해서 2로 나누는 것이다. 그런데 그렇게 되면 다시한번 반절을 가서, 1.5N의 여행을 해야한다는 단점이 있다. 여기서 우리는, 이전 문제에서 사용했던 two pointer를 사용하게 되면, 조금 더 효율적으로 풀어볼 수 있다. slower pointer와 faster pointer를 사용해서, 한 포인터는 한칸씩, 한 포인터는 두칸씩 가게 되면, 빠른 걸음을 걷는 포인터가 맨 끝, null에 도달했을 때, slower pointer는 중간 노드를 가르키고 있을것이다.

 

여기서 우리는, 어떻게 중간 노드를, "삭제" 할 수 있을지 생각해봐야한다. 삭제를 하기 위해서는 삭제 타겟이 되는 노드의 이전 노드의 next값을, 삭제 타겟이 되는 노드의 next노드로 설정해야 한다. 이렇게 되려면 우리는 faster pointer가 실제 null이 되기 전, 즉, faster pointer의 next가 null이거나, faster pointer의 next의 next가 null일때를 찾아서, slower pointer가 가르키고 있는 노드, 즉, 타겟노드의 그 전 노드의 next를 변경해주어야 한다. 여기서 포인터들을 head앞에 dummy node를 만들어, 가상의 출발점을 만들어주게 되면 보다 정확하게 가운데 노드를 찾아서 없애줄 수 있다.

 

코딩을 시작하기 전, Edge case도 고민해보자. head가 null이거나, head.next가 null이라면? 가운데 노드 삭제는 어떻게 해야할까? 여기서는 null을 리턴하는 로직으로 결정하고 진행해보자. 이제 이 로직을 코드로 나타내보자.

Node removeMidNode(Node head){
	if(head == null || head.next == null){
    	return head;
    }
    
    Node dummy = new Node(-1);
    dummy.next = head;
    
    Node slower = dummy;
    Node faster = dummy;
    
    while(faster.next != null && faster.next.next != null){
    	slower = slower.next;
        faster = faster.next.next;
    }
    
    slower.next = slower.next.next;
    return head;
}

 

이 알고리즘에서 Time Complexity는 O(N)이고, Space Complexity는 O(1)이다.

 

 

만약, 위 방식처럼 삭제 타깃 노드가 아닌, 삭제노드에만 접근할 수 있다면 어떻게 해야할까? 이럴 경우, 위 로직과 똑같지만, 멈추는 기준을 한스텝 더 가서, faster 또는 faster.next가 null일때로 하면, 해당 타겟 노드에 slower 노드가 있을것이고, 이 노드의 next를 next.next로 지정하되, next의 value를 현재의 value로 지정해주면 된다.

 

위의 로직과 거의 비슷하기 때문에, Time Complexity는 여전이 O(N)이고, Space Complexity는 O(1)이다.

Node removeMidNode(Node head){
	if(head == null || head.next == null){
    	return head;
    }
    
    Node dummy = new Node(-1);
    dummy.next = head;
    
    Node slower = dummy;
    Node faster = dummy;
    
    // while loop의 멈추는 조건을 변경해준다.
    while(faster != null && faster.next != null){
    	slower = slower.next;
        faster = faster.next.next;
    }
    
    // slower의 next val을 복사해서 지정해준다.
    slower.val = slower.next.val;
    slower.next = slower.next.next;
    return head;
}