要檢查鏈接列表作爲迴文沒有使用STACK

Question

下面是檢查如果鏈接列表是迴文是否代碼。我寫的代碼很簡單但仍冗長，因爲它有很多冗餘代碼。我是否可以REDUCE複雜性此代碼根據大O保持相同的邏輯。

只是因爲我不得不跳過的中間節點奇數鏈表我最終使得代碼冗餘的情況。只有我在奇鏈表的代碼添加額外的部分是

`head_new = temp->next; 

// NEEDED TO SHIFT ONE POSITION SINCE MIDDLE NODE DOES NOT NEED ANY CHECKING!!!` 

。

有沒有什麼辦法可以讓我的代碼整齊，少用多餘的代碼。

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; 
}