스택을 사용하지 않고 연결된 목록을 Palindrome으로 확인하려면

Question

연결 목록이 Palindrome 또는인지 확인하는 코드는 다음과 같습니다. 제가 작성한 코드는 매우 이고 아직 긴입니다. 많은 것으로서 REDUNDANT 코드입니다. REDUCE이 코드의 Big O과 같은 논리를 유지하면이 코드의 COMPLEXITY이 가능합니다. 내가 했기 때문에

그냥 내가 코드 중복을 결국 이상한 연결리스트의 경우에게 중간 노드를 건너 뜁니다. 홀수 연결 목록 용 코드에 추가 한 부분 만이

입니다.

코드를 깔끔하게 정리하고 중복 코드를 줄일 수있는 방법이 있습니까?

void linklist::palindrome() 
{ 
    node *prev = NULL; 
    node *curr = new node; 
    node *next = new node; 
    node *head_new = new node; 
    node *temp; 
    temp = head; 
    curr = head; 
    int t = 0,flag=0,flag_new=0; 
    while (curr != NULL) // calculating the length of llinked list 
    { 
     curr = curr->next; 
     t++; 
    } 
    curr = head; // Making sure curr is pointing to the head 
    if (t % 2 == 0) // checking whether the linked list is even or odd 
    { 
     flag = 1; 
    } 
    if (flag == 1) // if linked list is even 
    { 
     for (int i = 0; i < t/2 ; i++) // traversing till the half 
     { 
      temp = temp->next; 
     } 
     head_new = temp; // making sure head_new points to the head of other half 
     for (int i = 0; i < t/2; i++) // logic to do the reverse first half of the linked list 
     { 
      next = curr->next; 
      curr->next = prev; 
      prev = curr; 
      curr = next; 
     } 
     head->next = NULL; 
     head = prev; 
     while (head && head_new) // comparing the reversed first half with the second half 
     { 
      if (head->data != head_new->data) 
      { 
       cout << "Not palindrome"; 
       flag_new = 1; 
       break; 
      } 
      else 
      { 
       head = head->next; 
       head_new = head_new->next; 
      }   
     } 
     if (flag_new==0) 
     cout << "Palindrome"; 
    } 
    else 
    { 
     for (int i = 0; i < t/2; i++)// logic to do the traverse first half of the linked list 
     { 
      temp = temp->next; 
     } 
     head_new = temp->next; // ***NEEDED TO SHIFT ONE POSITION SINCE MIDDLE NODE DOES NOT NEED ANY CHECKING!!!*** 
     for (int i = 0; i < t/2; i++) // logic to do the reverse first half of the linked list 
     { 
      next = curr->next; 
      curr->next = prev; 
      prev = curr; 
      curr = next; 
     } 
     head->next = NULL; 
     head = prev; 
     while (head && head_new)// comparing the reversed first half with the second half 
     { 
      if (head->data != head_new->data) 
      { 
       cout << "Not palindrome"; 
       flag_new = 1; 
       break; 
      } 
      else 
      { 
       head = head->next; 
       head_new = head_new->next; 
      } 
     } 
     if (flag_new == 0) 
      cout << "Palindrome"; 

    } 
} 

Answer 1

도움이 될 수 있습니다 다음은 클래스에 링크 된 목록 관리 밖으로

int get_size(const node* n) 
{ 
    int res = 0; 
    while (n != 0) { 
     ++res; 
     n = n->next; 
    } 
    return res; 
} 

node* advance(node* n, int count) 
{ 
    for (int i = 0; i != count; ++i) { 
     n = n->next; 
    } 
    return n; 
} 

node* reverse(node* n, int count) 
{ 
    node* prev = nullptr; 
    for (int i = 0; i != count; ++i) { 
     node* next = n->next; 
     n->next = prev; 
     prev = n; 
     n = next; 
    } 
    return prev ? prev : n; 
} 

bool are_equal(const node* head1 , const node* head2) 
{ 
    const node* n1 = head1; 
    const node* n2 = head2; 
    for (; 
     n1 != nullptr && n2 != nullptr; 
     n1 = n1->next, n2 = n2->next) { 
     if (n1->data != n2->data) 
     { 
      return false; 
     } 
    } 
    return n1 == n2; 
} 


void linklist::palindrome() 
{ 
    const int t = get_size(head); 
    node *mid = advance(head, (t + 1)/2); 
    node* head2 = advance(mid, 1); 
    node* head1 = reverse(head, t/2); 

    if (are_equal(head1, head2)) { 
     std::cout << "Palindrome"; 
    } else { 
     std::cout << "Not palindrome"; 
    } 
    // Restore list 
    reverse(head1, t/2); 
    mid->next = head2; 
}