[알고리즘, Python] 연결 리스트에서 중간 노드 삭제하기

오늘은 Linked List 문제를 풀어보았다.

 

단방향 연결 리스트의 중간에 있는 노드 하나가 주어지면 그 노드를 삭제하는 문제다.

 

이 때 head에는 접근할 수 없고, 각 노드는 각기 다른 정수를 value로 가진다.

 

여기서 중간 노드라는 이야기는 정확하게 정중앙에 있는 노드라는 뜻이 아니라 맨 첫번째나 맨 끝이 아닌 노드, 즉 그 중간에 있는 노드들 중 하나라는 뜻이다.

 

문제는 여기서 확인할 수 있다.

https://leetcode.com/problems/delete-node-in-a-linked-list/

Delete Node in a Linked List - LeetCode

---

처음에 문제를 봤을 때는 당황스러웠다.

 

보통 단방향 링크드리스트에서 노드를 삭제할 때는 head부터 차례차례 next로 노드를 하나씩 거치면서 타겟 노드를 발견시 (타겟노드를 n이라 하자) n.previous.next = n.next 로 n을 삭제한다.

 

그런데 이 경우 head에 접근할 수 없고 단방향이므로, node.previous에는 접근할 수 없다는 뜻이 된다.

 

그러면 어떻게 이 문제를 해결할 수 있을까?

 

생각보다 해결방법은 금방 나왔다. 리트코드에서 보여지는 예제 그림 때문에 계속 previous 노드에 집착하거나 현재 있는 node를 리스트에서 삭제하는 이미지를 떠올리기 쉬운데, 그런 이미지를 버리자 쉽게 답을 생각해낼수 있었다.

 

바로 노드의 value를 다음 노드의 value로 바꾸고 마지막 노드는 삭제하면 된다.

 

이런 논리로 작성한 코드는 아래와 같다.

def deleteNode(self, node):
    while node.next.next != None:
        node.val = node.next.val
        node = node.next
    node.val = node.next.val
    node.next = None

실행 결과는 아래와 같다.

그런데 런타임이 그닥 좋지 않은 것을 알 수 있다.

 

그렇다면 어떻게 더 효율적으로 문제를 해결할 수 있을까?

---

내가 위에서 생각해낸 방법은 어쨌든 끝까지 노드를 다 탐색해서 value를 바꿔줘야한다.

 

하지만 그럴 필요없이 더 간결한 방법으로 문제를 해결할 수 있었다.

def deleteNode(self, node):
    node.val = node.next.val
    node.next = node.next.next

바로 타겟 노드의 value를 next 노드의 value로 바꾼 후 그 다음 노드를 삭제하면 된다.

 

아이디어는 아래 글에서 참고했다.

https://leetcode.com/problems/delete-node-in-a-linked-list/discuss/469072/PythonGo-by-victim-node-operation-w-Visualization

 

아무래도 이게 가장 좋은 방법인 것 같은데 어째서인지 실행 결과 런타임에 크게 차이는 없었다.

 

그래도 시간 복잡도를 계산해보자면 내가 처음 생각해낸 방법은 O(n)이고 두번째 방법은 O(1)이 될 것이다.

---

출처

 

모두 본문에 포함