[알고리즘] Remove Nth Node From End of List

Leetcode의 Remove Nth Node From End of List 문제를 풀어보도록 하겠습니다.

문제

링크드 리스트가 주어졌을 때, 끝에서 n번째 노드를 제거 후, 그 링크드 리스트의 헤드를 리턴하라.

예를 들어, 링크드 리스트가 1->2->3->4->5이고 n이 2라면, 1->2->3->5를 리턴해야 한다.
왜냐하면 끝에서 2번째 노드는 4이기 때문이다.

풀이 1: 루프 2번 돌리기

앞에서 n번째 노드를 제거하는 문제라면 좀 쉬웠을텐데, 끝에서 n번째 노드를 제거해야 하는 살짝 더 까다로운 문제입니다.
왜냐하면 궁긍적으로 링크드 리스트를 끝까지 따라가보지 않고서는 어디가 끝인지 알수가 없기 떄문입니다.
따라서 이 문제는 적어도 O(N) 시간 복잡도를 가지는 알고리즘을 필요로 한다는 것을 알 수 있습니다.

가장 단순하게 생각해낼 수 있는 풀이 방법은 링크드 리스트를 끝까지 따라가서 길이를 먼저 알아낸 후, 다시 처음부터 삭제할 노드까지 따라가는 것입니다.
링크드 리스트의 길이를 l이라고 한다면, 처음부터 l - n - 1 만큼 떨어진 곳에 삭제할 노드가 위치할 것입니다.
따라서, 삭제할 노드의 바로 앞에 있는 l - n - 1 번째 노드의 다음 노드를 l - n + 1 번째로 바꿔줘야 합니다.

Python 코드

먼저, n0인 경우에는 삭제할 노드가 없으므로 입력받은 링크드 리스트를 그대로 리턴하면 됩니다.
그 다음, 첫번째 while 루프로 링크드 리스트를 끝까지 따라가서 링크드 리스트의 길이(즉, 모든 노드의 개수)를 구합니다.
다음 while 루프에서는 다시 링크드 리스트의 처음부터 l - n 번째 노드까지 찾아 갑니다.
마지막으로 l - n - 1 번째 노드의 next 필드를 l - n + 1 번째 노드로 업데이트 해줍니다.

여기서 한가지 코딩팁은 dummy 노드를 사용해서 링크드 리스트에서 흔히 겪는 Edge Case를 깔끔하게 처리할 수 있다는 것입니다.
이렇게 dummy 노드를 사용하면 링크드 리스트에 노드가 하나 밖에 없거나 head 자체를 삭제해야하는 경우에도 버그를 피할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def removeNthFromEnd(self, head, n):
if n == 0:
return head

length = 0
node = head
while node:
length += 1
node = node.next

dummy = ListNode(None)
dummy.next = head
node = dummy
while length > n:
node = node.next
length -= 1
node.next = node.next.next

return dummy.next

Java 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n == 0) return head;

int length = 0;
ListNode node = head;
while (node != null) {
length += 1;
node = node.next;
}

ListNode dummy = new ListNode(-1);
dummy.next = head;
node = dummy;
while (length - n > 0) {
node = node.next;
length--;
}
node.next = node.next.next;

return dummy.next;
}
}

복잡도

이 풀이 방법은 링크드 리스트를 총 2번 루프를 돌긴 하지만 Big O 기준으로는 L을 링크드 리스트의 길이라고 했을 때 O(L) 시간 복잡도를 가집니다.
그리고 n 값이 클 수록 l - n이 작아지므로, 두번째 루프가 성능에 미치는 영향이 점점 작아진다는 특성을 가지고 있습니다.
반대로 링크드 리스트의 길이가 엄청 긴데 n 값이 작으면 성능이 매우 떨어지게 됩니다.
공간 복잡도는 추가적인 메모리는 사용하지 않기 때문에 O(1) 입니다.

풀이 2: 루프를 1번만 돌리면서 모든 노드를 저장하기

만약에 면접관이 루프를 한 번만 돌려서 이 문제를 풀 수 없겠냐고 물어본다면 어떻게 접근해야 할까요?
많은 경우, 공간 복잡도를 희생하면 시간 복잡도를 향상시킬 수 있기 때문에 어떤 자료구조를 사용할 수 있을지 생각해보면 도움이 됩니다.
이 문제의 경우, 링크드 리스트를 순회하면서 모든 노드를 인덱스로 접근을 지원하는 또 다른 자료 구조에 저장해둘 수 있습니다.
따라서 모든 노드를 리스트에 저장한 후에 l - n - 1 번째 노드의 next 필드를 l - n + 1 번째 노드로 업데이트해주면 됩니다.


Python

파이썬의 내장 리스트는 음수 인덱스로 원소 접근이 가능합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def removeNthFromEnd(self, head, n):
if n == 0:
return head

dummy = ListNode(None)
dummy.next = head

nodes = [dummy]
node = head
while node:
nodes.append(node)
node = node.next
nodes[-n - 1].next = nodes[-n + 1] if n > 1 else None

return dummy.next

Java

자바의 내장 리스트는 음수 인덱스로 원소 접근을 지원하지 않습니다.
따라서 size() 메서드로 리스트의 길이를 구한 후 양수 인덱스로 원소에 접근해야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n == 0) return head;

ListNode dummy = new ListNode(-1);
dummy.next = head;

List<ListNode> nodes = new ArrayList<>();
nodes.add(dummy);

ListNode node = head;
while (node != null) {
nodes.add(node);
node = node.next;
}

int length = nodes.size();
nodes.get(length - n - 1).next = n > 1 ? nodes.get(legnth - n + 1) : null;

return dummy.next;
}
}

복잡도

이 풀이 방법은 링크드 리스트를 총 1번 루프를 돌긴 하지만 Big O 기준으로는 첫번째 풀이법 동일한 O(L) 시간 복잡도를 가집니다.
반면, 주어진 링크드 리스트와 동일한 길이의 추가 자료 구조를 사용하기 때문에 공간 복잡도는 O(L)으로 첫번째 풀이법보다 오히려 안 좋습니다.
하지만 링크드 리스트의 길이가 엄청나게 길고, 가용 메모리가 충분한 상황이라면 첫번째 알고리즘보다 속도는 더 빠를 것입니다.

풀이 3: 루프를 1번만 돌리면서 n개의 노드만 저장하기

두번째 풀이 방법에서 O(L) 공간 복잡도가 다소 아쉬웠는데요… 공간 복잡도를 개선할 여지가 있는지 한 번 생각해보겠습니다.
구지 모든 노드를 저장할 이유가 있을까요?
조금만 더 생각해보면 끝에서 n번째 노드를 제거하기 위해서는 n개의 노드만 저장해도 충분하다는 것을 깨닫게 됩니다.
n개의 노드만 저장하려면 링크드 리스트를 루프 돌다가 저장 공간의 크기가 n을 초과할 경우 가장 오래된 노드를 제거해야합니다.
이럴 때 적합한 자료구조는 FIFO(First In First Out)를 제공하는 큐(Queue)입니다.

링크드 리스트를 루프를 돌 때 큐의 길이를 체크해서 n보다 클 경우, 가장 오래된 노드를 큐에서 제거하고 새로운 노드를 추가합니다.
루프가 끝나면 큐에 저장된 첫번째 노드의 next 필드를 큐에 저장된 세번째 노드로 업데이트해주면 됩니다.

Python

파이썬의 내장 리스트의 pop(0) 함수를 사용하면 마치 큐처럼 사용할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def removeNthFromEnd(self, head, n):
if n == 0:
return head

dummy = ListNode(None)
dummy.next = head

nodes = [dummy]
node = head
while node:
if len(nodes) > n:
nodes.pop(0)
nodes.append(node)
node = node.next
nodes[0].next = nodes[2] if n > 1 else None

return dummy.next

Java

자바에서는 LinkListQueue 인터페이스 구현체이기 때문에 사용하기 적합합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n == 0) return head;

ListNode dummy = new ListNode(-1);
dummy.next = head;

LinkedList<ListNode> nodes = new LinkedList<>();
nodes.add(dummy);

ListNode node = head;
while (node != null) {
if (nodes.size() > n)
nodes.remove();
nodes.add(node);
node = node.next;
}

nodes.get(0).next = n > 1 ? nodes.get(2) : null;
return dummy.next;
}
}

복잡도

이 풀이 방법을 통해 공간 복잡도를 O(L)에서 O(N)으로 개선할 수 있게 되었습니다.

풀이 4: 루프를 1번만 돌리기

아예 추가 공간을 사용하지 않고 루프를 한 번만 돌 수 있는 방법은 없을까요?
링크드 리스트를 두개의 포인터를 사용해서 순회하면 가능합니다!
일단 첫번째 포인터를 먼저 n만큼 진행 시킵니다.
그리고 첫번째 포인터가 링크드 리스트의 끝에 다다를때까지 첫번째 포인터와 두번째 포인터를 동시에 진행 시킵니다.
그럼 두번째 포인터는 자연스럽게 끝에서 n번째 노드를 가르키게 됩니다!


Python

두번째 포인터는 dummy부터 루프를 도는 것에 주의바랍니다.
위에서 설명드린 링크드 리스트의 Edge case를 피하기 위함이기도 히지만, 두번째 포인터가 끝에서 n 번째가 아닌 n - 1 번째를 가리키도록 하기위한 의도도 있습니다.
그래야 n 번째 노드를 삭제하기가 용이하기 때문입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def removeNthFromEnd(self, head, n):
if n == 0:
return head

first = head
for _ in range(n):
first = first.next

dummy = ListNode(None)
dummy.next = head

second = dummy
while first:
first = first.next
second = second.next

second.next = second.next.next
return dummy.next

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n == 0) return head;

ListNode first = head;
for (int i = 0; i < n; i++) {
first = first.next;
}

ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode second = dummy;

while (first != null) {
first = first.next;
second = second.next;
}

second.next = second.next.next;
return dummy.next;
}
}

복잡도

이 풀이 방법을 통해 공간 복잡도를 O(N)에서 O(1)으로 개선할 수 있게 되었습니다.

마치면서

많은 코딩 면접관들이 이 문제처럼 다양한 해결 방법을 가진 문제를 내는 것을 선호합니다.
왜냐하면 추가적인 제약사항을 제시하면서 지원자가 어떻게 문제를 해결하는지 평가하기 좋기 때문입니다.

문제 출처

공유하기