정렬 된 목록 II에서 중복 제거  


난이도 중급
자주 묻는 질문 아마존
연결된 목록

"정렬 된 목록 II에서 중복 제거"문제는 중복 요소가있을 수도 있고 없을 수도있는 연결 목록이 제공된다는 것을 나타냅니다. 목록에 중복 요소가있는 경우 목록에서 해당 인스턴스를 모두 제거하십시오. 다음 작업을 수행 한 후 마지막에 연결 목록을 인쇄합니다.

예  

정렬 된 목록 II에서 중복 제거

Elements of linked list: 1 2 2 2 3 5 7 7
List after removing all the elements: 1 3 5

설명

숫자 2에는 목록에 3 개의 인스턴스가 있습니다. 따라서 우리는 모든 인스턴스를 제거했습니다. 숫자 7에서도 마찬가지입니다. 따라서 2와 7의 모든 인스턴스를 제거한 후 3 1 3 인 5 개의 요소 만 남았습니다.

접근  

이미 언급했듯이 "정렬 된 목록 II에서 중복 제거"문제는 목록에 중복이있는 모든 번호를 제거하도록 요청합니다. 한 번 논의 된 문제가있었습니다. 그러나 현재 문제에는 약간의 차이가 있습니다. 이전 문제는 우리에게 중복 만 삭제. 즉, 중복을 삭제했지만 중복이있는 요소의 단일 사본은 제거되지 않았습니다. 여기서 우리는 각각의 모든 사본과 목록에 중복 된 원본 요소를 삭제해야합니다.

이제 우리는 문제에 대해 잘 알고 있습니다. 문제를 해결하는 방법을 생각할 수 있습니다. 우리는 이미 목록이 정렬되어 있음을 알고 있습니다. 그래서 우리는이 사실을 사용할 수 있습니다. 목록이 정렬되면 중복이 있는지 확인합니다. 그들은 항상 그룹에서 발생합니다. 따라서 인접한 요소의 중복 여부 만 확인하면됩니다. 그런 쌍을 만나면. 먼저, 중복되지 않는 요소를 찾거나 목록이 끝날 때까지 목록을 탐색합니다. 그 시점에서 우리는 이전 노드를이 새로운 중복되지 않는 요소를 가리 킵니다. 그런 다음 다시이 중복되지 않은 요소에서 중복 요소 검색을 시작합니다.

참조
프림의 알고리즘

"비 중복"이라는 용어는 현재 요소가 목록에 중복되지 않음을 의미하지 않습니다. 현재 노드가이 요소와 같지 않음을 의미합니다. 목록에 1, 2, 2, 2, 3, 3이 있다고 생각해보십시오. 우리는 1 대 3을 가리 킵니다. 그러나 3도 제거됩니다. 그러나 어느 시점에서 우리는 인접한 요소를 확인하고 처음 2 2 쌍을 발견했습니다. 3은 2가 아니기 때문에 중복되지 않는다고 말합니다.

그래서 이것을 요약합니다. 우리는 단순히 목록을 순회합니다. 다음 요소가 현재 요소와 동일한 지 계속 확인하십시오. 이 경우 중복되지 않는 요소를 찾을 때까지 계속 요소를 제거하십시오.

암호  

정렬 된 목록 II에서 중복을 제거하는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL || head->next==NULL)
        return head;
    ListNode* prev = create(-1);
    ListNode* dummy = prev;
    ListNode* cur = head;
    prev->next = cur;
    while(cur && cur->next) {
        if(cur->data == cur->next->data) {
            while(cur->next && cur->data==cur->next->data) {
                ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}

void printLinkedList(ListNode *headA){
  while(headA != NULL){
    cout<<headA->data<<" ";
    headA = headA->next;
  }
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  headA->next->next = create(2);
  headA->next->next->next = create(2);
  headA->next->next->next->next = create(3);
  headA->next->next->next->next->next = create(5);
  headA->next->next->next->next->next->next = create(7);
  headA->next->next->next->next->next->next->next = create(7);

  headA = deleteDuplicates(headA);
  printLinkedList(headA);
}
1 3 5

정렬 된 목록 II에서 중복을 제거하는 Java 코드

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

  static ListNode deleteDuplicates(ListNode head) {
      if(head==null || head.next==null)
          return head;
      ListNode prev = create(-1);
      ListNode dummy = prev;
      ListNode cur = head;
      prev.next = cur;
      while(cur != null && cur.next != null) {
          if(cur.data == cur.next.data) {
              while(cur.next != null && cur.data==cur.next.data) {
                  ListNode tmp = cur;
                  cur = cur.next;
              }
              prev.next = cur.next;
              cur = prev.next;
          } else {
              prev = cur;
              cur = cur.next;
          }
      }
      return dummy.next;
  }

  static void printLinkedList(ListNode headA){
    while(headA != null){
      System.out.print(headA.data+" ");
      headA = headA.next;
    }
  }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    headA.next.next = create(2);
    headA.next.next.next = create(2);
    headA.next.next.next.next = create(3);
    headA.next.next.next.next.next = create(5);
    headA.next.next.next.next.next.next = create(7);
    headA.next.next.next.next.next.next.next = create(7);

    headA = deleteDuplicates(headA);
    printLinkedList(headA);
  }
}
1 3 5

복잡성 분석  

시간 복잡성

의 위에), 정확히 하나의 요소를 순회하고 있기 때문입니다. 따라서 시간 복잡도는 선형입니다.

참조
이중 연결 목록을 사용한 Deque 구현

공간 복잡성

O (1), 상수 요소를 사용했기 때문입니다. 따라서 공간 복잡성은 일정합니다.