배열에 있는 연결 목록에서 노드 삭제

3217. 배열에 있는 연결 목록에서 노드 삭제

난이도:중

주제: 배열, 해시 테이블, 연결 목록

정수 배열과 연결 목록의 헤드가 제공됩니다. 연결 리스트에서 nums에 존재하는 값을 가진 모든 노드를 제거한 후 수정된 연결 리스트의 헤드를 반환합니다.

예 1:

• 입력: nums = [1,2,3], head = [1,2,3,4,5]
• 출력: [4,5]
• 설명: 값이 1, 2, 3인 노드를 제거합니다.

예 2:

• 입력: 입력: nums = [1], head = [1,2,1,2,1,2]
• 출력: [2,2,2]
• 설명: 값이 1인 노드를 제거합니다.

예 3:

• 입력: nums = [5], head = [1,2,3,4]
• 출력: [1,2,3,4] 값이 5인 노드는 없습니다.

제약조건:

• 1 5
• 1 5
• nums의 모든 요소는 고유합니다.
• 주어진 목록의 노드 수는 [1, 10⁵] 범위에 있습니다.
• 1 5
• 연결된 목록에 nums에 없는 값을 가진 노드가 하나 이상 있도록 입력이 생성됩니다.

힌트:

1. 숫자의 모든 요소를 ​​세트에 추가합니다.
2. 목록을 스캔하여 설정을 확인하여 현재 요소를 삭제해야 하는지 확인하세요.

해결책:

연결된 목록을 탐색하여 nums 배열에 값이 있는 모든 노드를 제거해야 합니다.

접근하다:

1. 빠른 조회를 위한 해시 세트: nums에 값이 있는지 확인하는 것이 효율적이어야 하므로 nums를 해시 세트로 변환하겠습니다. 이를 통해 각 값에 대해 O(1) 조회가 가능합니다.
2. 연결된 목록을 통해 반복: 연결된 목록을 반복하고 해시 세트에 값이 있는 노드를 제거합니다.
3. 포인터 조작: 반복하는 동안 nums 배열의 값과 일치하는 노드를 "건너뛰기" 위해 포인터를 조정합니다.

단계:

1. 숫자를 O(1) 조회를 위한 해시 세트로 변환합니다.
2. 두 개의 포인터를 사용하여 연결 목록을 탐색합니다. 하나는 현재 노드용이고 다른 하나는 이전 노드용이므로 노드를 효율적으로 제거하는 데 도움이 됩니다.
3. 각 노드에 대해 해당 값이 해시 세트에 있는지 확인하세요. 그렇다면 이전 노드의 다음을 업데이트하여 현재 노드를 건너뜁니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3217. 배열에 있는 연결 목록에서 노드 삭제

<?php // Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @param ListNode $head
     * @return ListNode
     */
    function removeElements($head, $nums) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

// Example usage:

// Linked List: 1 -> 2 -> 3 -> 4 -> 5
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

// Array nums: [1, 2, 3]
$nums = [1, 2, 3];

$solution = new Solution();
$result = $solution->removeElements($head, $nums);

// Function to print the linked list
function printList($node) {
    while ($node !== null) {
        echo $node->val . " ";
        $node = $node->next;
    }
}

// Print the resulting linked list
printList($result); // Output: 4 5
?>

설명:

1. removeElements($head, $nums):

   • 빠른 조회를 위해 먼저 숫자를 해시 세트($numSet = array_flip($nums);)로 변환합니다.
   • 더미 노드가 생성되어 목록의 선두에 연결됩니다. 이는 헤드 노드 제거와 같은 극단적인 경우를 단순화하는 데 도움이 됩니다.
   • 이전 포인터는 현재 노드 이전의 노드를 추적하므로 목록에서 현재 노드를 건너뛰어 제거할 수 있습니다.
   • 각 노드에 대해 해당 값이 numSet에 있는지 확인합니다. 그렇다면 현재 노드를 건너뛰도록 prev->next 포인터를 조정하여 제거합니다.

2. 최첨단 케이스:

   • 헤드 노드를 제거해야 하는 경우 더미 노드는 헤드가 깔끔하게 제거되고 올바른 목록을 반환할 수 있도록 보장합니다.
   • 연속된 여러 노드를 제거해야 하는 경우를 처리합니다.

3. 복잡성:

   • 시간 복잡도: O(n), 여기서 n은 연결 목록의 노드 수입니다. 우리는 각 노드를 한 번씩 방문합니다. 숫자를 집합으로 변환하는 데는 O(m)이 소요됩니다. 여기서 m은 숫자의 크기입니다.
   • 공간 복잡도: 숫자 집합을 저장하는 데는 O(m)입니다.

예제 연습:

입력 숫자 = [1, 2, 3] 및 헤드 = [1, 2, 3, 4, 5]의 경우 알고리즘은 다음을 수행합니다.

• 노드 1에서 시작하여 1이 숫자인지 확인한 후 제거하세요.
• 노드 2로 이동하여 2가 숫자인지 확인한 후 제거하세요.
• 노드 3으로 이동하여 3이 숫자인지 확인한 후 제거하세요.
• 숫자가 아닌 노드 4, 5로 이동하여 목록에 남습니다.

결과 연결 리스트는 [4, 5]입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 배열에 있는 연결 목록에서 노드 삭제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!