재귀를 사용하여 정렬된 연결 목록에서 중복 제거

연결된 목록은 서로 연결된 일련의 요소입니다. 각 목록에는 헤더와 일련의 노드가 있으며, 각 노드는 현재 노드에 대한 데이터를 보유하고 다음 노드에 연결됩니다. 연결리스트의 기본 연산은 삽입, 삭제, 검색, 삭제이다.

정렬된 연결 목록에서 중복 제거

노드를 삭제하는 한 가지 방법은 재귀를 사용하는 것입니다. 아이디어는 각 노드를 인접 노드와 비교하고 동일한 중복 노드를 제거하는 것입니다.

재귀 호출은 다음 노드로 돌아갑니다. 따라서 다음 요소에 대해 current_node->next = our_function(node->next)와 같은 재귀 함수를 호출합니다.

우리는 재귀를 신뢰하며 current_node->next에는 이제 중복 요소 없이 연결된 목록이 포함됩니다.

주요 방법에서는 처음부터 목록에 입찰합니다 -

으아아아

알고리즘

정렬된 연결리스트에서 중복을 제거하기 위해 재귀를 사용하는 과정은 다음과 같습니다.

• 1단계 - 모든 값이 순서대로 정렬된 연결 목록 만들기

• 2단계 - 연결리스트가 존재하지 않으면 프로그램이 종료됩니다.

• 3단계 - 연결리스트가 존재한다면 헤드 노드의 다음 값과 헤드 노드의 값을 비교합니다. 두 값이 동일하면 헤더를 제거하십시오.

• 4단계 - 3단계는 재귀적으로 수행됩니다. 목록이 자체에서 모든 중복 값을 제거할 때까지 각 노드를 헤드로 처리합니다.

• 5단계 - 얻은 출력은 다양한 값을 가진 정렬된 연결 목록입니다 ​​

예

예를 들어 다음 값을 가진 정렬된 연결 목록이 있습니다. ​​-

1->1->1->2->3->3->4

재귀를 사용하여 위의 정렬된 연결 목록에서 중복 항목을 제거하는 C++ 프로그램을 살펴보겠습니다. -

으아아아

이후에는 현재 노드가 연결리스트에 포함되어 있는지 확인합니다. 현재 노드 -> 다음 노드에서 얻은 만족스러운 연결 목록이 해당 노드와 동일한 값을 갖는 경우 해당 노드를 포함하지 않고 포함합니다.

NOTE - 현재 노드가 NULL인 경우 재귀의 기본 조건을 반환합니다.

출력

으아아아

결론

재귀 호출에서 살펴본 것처럼 우리는 다음 호출이 나머지 문제의 예상 결과를 달성할 것이라고 믿습니다. 방금 현재 하위 문제를 해결했습니다. 이를 염두에 두고 현재 요소가 포함될 수 있는지 확인하고 나머지 연결 목록을 재귀 호출에 넘겨 해당 지점부터 유효한 연결 목록을 제공할 것이라고 믿습니다. 연결리스트 전체를 순회할 때, 우리 방법의 시간복잡도는 O(n)이다.

위 내용은 재귀를 사용하여 정렬된 연결 목록에서 중복 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!