237. Delete Node in a Linked List

단순 연결 리스트에서 노드를 삭제하는 함수를 작성하는 문제다.
head에 대한 접근 권한 대신에 삭제할 노드에 대한 접근 권한을 가지며 삭제할 노드가 마지막 노드가 아니라는 것이 보장된다.

Solution

보자마자 엥? 제거면 그냥 node = node.next 하면 되는거 아님? 하면서 바로 RUN을 해봤는데 오답이었다.

오답인 이유는 실제 노드를 삭제하지 않고 다음 노드로 대체시킬 뿐이라서 그렇다. 우리는 head의 정보 없이 현재 노드 정보만 알고 있다. 이 node에 다음 node를 덮어씌워봤자 지금 내 노드 앞의 노드, prev의 입장에서보면 prev.next는 여전히 이전의 노드를 가리키고 있다.

그래서 대체가 아닌 해당 노드의 val과 next의 값을 직접 바꿔줘야 정답이다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

시간 복잡도

두 번의 연산이 끝이니까 O(1)