leetCode (Remove Linked List Elements)-LinkedList

문제

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

 

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]

 

---

배경지식

연결리스트 - 원소들을 저장할 때, 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조.

• 특징
  • k번째 원소를 확인/변경하기 위해 O(k(가 필요함
  • 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
  • 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

 

문제해결

• current, prev라는 변수를 두어 head를 참조하도록 설정
• current가 움직이면서 각 노드의 값을 주어진 val 값을 비교
• prev가 처음에는 null임. 이 때의 current node의 값과 val의 값이 같을 경우, head를 current.next부터 참조하도록 지정
•  prev가 존재할 때 current node의 값과 val의 값이 같을 경우, prev의 next값을 current next 값으로 변경 ( prev가 head를 참조하기 때문에, prev를 변경시키면 head도 변경된다)

 

구현

var removeElements = function (head, val) {
    let prev = null, current = head;
    while (current) {
        if (current.val === val) {
            if (!prev) {
                head = current.next;
            } else {
                prev.next = current.next;
            }
        } else {
            prev = current;
        }
        current = current.next
    }
    return head;
};

---

느낀점

• 처음에는 return 되는 head값이 언제 변경되는 지 이해가 되지 않았음.
• 참조하는 개념을 명확히 몰랐던 것임.
• 덕분에, 객체끼리 참조하는 개념을 배울 수 있었음.