Linked List | Delete Node in a Linked List

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.


Constraints:
* The number of the nodes in the given list is in the range [2, 1000].
* -1000 <= Node.val <= 1000
* The value of each node in the list is unique.
* The node to be deleted is in the list and is not a tail node

LinkedList에서 노드를 삭제하는 문제이다. tail일 경우도 해결할 수 있지만, 이 문제에서는 tail 노드는 아니라는 조건을 줬다. Node의 val은 integer이고, -1000부터 1000까지이다. 노드의 갯수는 2개에서 1000개사이이다. 각 노드의 value는 unique하다. 

 

이 문제는 단 두줄로 해결을 할 수 있다.

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

* Time Complexity: O(1)

* Space Complexity: O(1)

Tail노드가 아니라는 조건이 있기 때문에, next node에 있는 val을 복사 후, 현재 노드의 next값을 next의 next로 지정해주면 된다.

 

 

분석 결과, 속도는 최상위 속도로 빨랐고, 메모리는 전체 submissions에서 47.23%에 해당했다. 다른 언어로 테스트 했을땐, 메모리 사용량을 낮출 수 있지만, 속도는 더 느려졌다. (다른 유저의 솔루션 참고)

포켓몬 4마리가 있는 LinkedList가 있다면! 이상해씨 자리에 파이리를 복제하고 (ㅠㅠ...) 이상해씨가 피카츄와 손을 잡으면 이상해씨는 사라진다! 파이리를 보내주려면? 파이리 자리에 피카츄를 복제하고 피카츄와 꼬부기가 손을 잡으면 된다. 말하고 나니까 포켓몬들에게 미안해진다. 미안 애들아 알고리즘 공부는 요렇게 해야 잘 이해가 되서 그래...

 

 

 

Reference

Delete Node in a Linked List - LeetCode

 

Pokemon friends by WolverineGirl7 on DeviantArt