단일 링크 된 목록에서 m 노드 삭제

Question

bool DeleteMNodes (int x, int m) 코드를 작성하십시오. 이 함수는 값이 x 인 첫 번째 m 노드를 삭제합니다. 값이 x 인 노드가 하나 이상 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. 그렇지 않으면 false를 반환합니다. 값이 x 인 노드 수가 m보다 작은 경우 값이 x 인 모든 노드를 삭제합니다. 이 함수는 O(n)에서 실행되어야합니다. 여기

는 SSL 노드의 클래스입니다 :

class IntSLLNode 
{ 
public: 
    int val; 
    IntSLLNode* next; 

    IntSLLNode(int val,IntSLLNode* next); 
    ~IntSLLNode(); 
}; 

그리고 이것은 SSL 클래스입니다 :

bool IntSLList::DeleteMNodes(int x, int m) 
{ 
    IntSLLNode *pred, *tmp, *delNode; 
    int count=0; 
    if (IsEmpty()) 
     return false; 

    if (count <= m) { 
     if (head->val == x) { 
      DeleteFromHead(); 
      count++; 
     } 
    } 

    for (pred=head, tmp=head->next; tmp!=NULL;) 
    {  
     if (count <= m) 
     { 
      if (tmp->val == x) 
      { 
       delNode = tmp; 
       pred->next = tmp->next; 
       tmp = tmp->next; 
       delete delNode; 
       count++; 
      } 
      else { 
       pred = pred->next; 
       tmp = tmp->next; 
      } 

     } 
    } 
    if (count>=1) 
     return true; 
    else 
     return false; 
    } 
} 

그러나 :

여기

class IntSLList 
{ 
public: 
    IntSLList(); 
    ~IntSLList(); 

    bool IsEmpty(void); 
    void AddToHead(int val); 
    void AddToTail(int val); 
    void DeleteFromHead(void); 
    void DeleteFromTail(void); 
    bool DeleteNode(int val); 
    bool IsInList(int val); 
    bool DeleteMNodes (int x, int m); //My function 
    void Print(); 

private: 
    IntSLLNode *head, *tail; 
}; 

이 DeleteMNodes(int x, int m) 기능의 내 구현 그것은 작동하지 않습니다!. 뭐가 잘못 됐어?

Answer 1

카운트 도달 후 포인터가 앞으로 나아 가지 않습니다. 예를 들면 다음과 같은 몇 가지 옵션이 있습니다.

for (pred=head, tmp=head->next; tmp!=NULL;) 
{  
    bool didDelete = false; 
    if (count <= m) 
    { 
     if (tmp->val == x) 
     { 
      delNode = tmp; 
      pred->next = tmp->next; 
      tmp = tmp->next; 
      delete delNode; 
      count++; 
      didDelete = true; 
     } 
    } 

    if(!didDelete) 
    { 
     pred = pred->next; 
     tmp = tmp->next; 
    } 
} 

또는 m == 카운트를 한 번 깰 수 있습니다.

for (pred=head, tmp=head->next; tmp!=NULL;) 
{  
    if (count <= m) 
    { 
     if (tmp->val == x) 
     { 
      delNode = tmp; 
      pred->next = tmp->next; 
      tmp = tmp->next; 
      delete delNode; 
      count++; 
     } 
     else { 
      pred = pred->next; 
      tmp = tmp->next; 
     } 
    } 
    else { 
     break; 
    } 
} 

필자는 불필요한 반복을 피하기 때문에 마지막으로 선호합니다.