[Leetcode] 19번 - Remove Nth Node From End of List

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
• 문제: 마지막 노드로부터 n번째 노드를 삭제하고 head를 반환해라.
• 시간복잡도 파악: 연결리스트의 입력 크기가 30이라서 O(N) 이내어야한다.

 

2. 입출력 케이스 도출

• 일반 케이스: head = [1,2,3,4,5], n = 2 -> [1,2,3,5], head = [1,2], n = 1 -> [1]
• 엣지 케이스: head = [1], n = 1 -> [], head = [1,2], n = 2 -> [2]

 

3. 핵심 문제 풀이 도출

연결리스트의 끝에서 n번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를 순차대로 push해서 pop하면 끝에서붙 노드를 가져올수있다.

그리고 연결리스트의 끝에서 n+1 번째 노드를 찾아 next 참조 변수로 삭제할 노드를 건너뛰고 연결할 노드를 참조할수있다. 그래서 (끝에서 n+1번째 노드).next = (끝에서 n+1번째 노드).next.next를 수행하면 끝에서 N번째 노드를 삭제할수있다.

주의할것은 엣지 케이스를 보면, 삭제할 노드가 head일 경우에 head.next를 반환하면된다. 이때는 n값이 연결리스트의 개수가 같을때이다. 즉, 스택에 연결리스트의 노드를 모두 push한 후 스택 크기가 n가 동일하면, head.next를 반환하면된다.

 

4. 코드로 문제 풀이 구현

1. 모든 노드를 순회하면서 스택에 push()한다.
2. 스택의 크기가 n이면 head.next를 반환한다.
3. 스택의 노드를 n만큼 pop()한다.
4. 끝에서 n+1 번째 노드를 가져와서 next 필드로 n-1번째 노드와 연결한다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;

        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        // 1. 노드의 개수가 n과 동일할 경우에는 head 삭제해야하므로, head = head.next 저장한후에 head.next 반환
        if (n == stack.size()) {
            return head.next; // head를 삭제해야 하는 경우
        }

        // 2. 끝에서 n번재까지 노드까지 pop
        for (int i = 0; i < n; i++) {
            stack.pop();
        }

        // 3. 끝에서 n+1 번째 노드를 가져와서 next 필드로 n-1번째 노드와 연결
        ListNode prev = stack.peek();
        prev.next = prev.next.next;

        return head;
    }

}

 

5. 다른 문제 풀이

끝에서 n번째 노드는 처음부터 l-n+1번째 노드이다.

# l = 5
# n = 2
# v는 삭제할 노드
# 맨처음 노드부터 4(5 - 2 + 1)번째 노드

      v
1 2 3 4 5

 

연결리스트 길이가 l이면, fast 포인터를 n만큼 먼저 이동시킨다. 그러면 fast 포인터가 마지막 노드에 도달할려면 l-n-1만큼 움직이면된다. 따라서 이상태에서 slow포인터는 head에서 시작하고 fast를 마지막 노드까지 하나씩 이동시킨다면, slow 포인터는 head부터 l-n-1만큼 움직이게된다. 그러므로 삭제할 노드의 직전 노드까지 이동할수있는것이다. 이렇게 투 포인터로 풀수있으며, 위의 스택을 사용한 풀이에서는 시간 복잡도는 O(N)으로 동일하지만, 공간 복잡도가 O(N)이었으나 여기서는 O(1)이다.

# l = 5
# n = 2
# n 만큼 이동

f  
1 2 3 4 5

    f  
1 2 3 4 5

s   f
1 2 3 4 5

    s   f
1 2 3 4 5

 

1. fast 포인터를 n칸 먼저 이동시킨다.
2. 그런 상태에서 slow포인터는 head부터 시작해서 fast와 slow를 동시에 한 칸씩 이동한다.
3. 그러면 fast가 끝에 도달할 때 slow는 삭제할 노드의 이전 노드에 도달하게 된다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // n이 연결리스트의 길이와 같으면 head 삭제
        if (fast == null) {
            return head.next; 
        }

        // slow는 삭제할 노드의 이전노드로 업데이트
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 삭제할 노드를 건너띠고 연결
        slow.next = slow.next.next; 

        return head;
    }
}

 

6. 복잡도

1. Stack 풀이
   • 시간복잡도: O(N)
   • 공간복잡도:O(N)
2. 투포인터 풀이
   • 시간복잡도: O(N)
   • 공간복잡도: O(1)