Обращение связанного списка влияет на указатель заголовка исходного списка в main (). Поэтому не удалось сравнить перевернутый список и оригинальный список - C ++

Question

Я пишу программу, чтобы проверить, является ли односвязный список палиндромом или нет. Для этого я хочу перевернуть список и сравнить его с исходным списком. Но я столкнулся со следующей проблемой - когда я переворачиваю список, указатель заголовка исходного списка изменяется и указывает на NULL. Итак, когда у меня есть следующий исходный список, после обращения исходного списка происходит следующее:

1. Исходный список: 1-> 1-> 2-> 1-> NULL
2. Перевернутый list: 1-> 2-> 1-> 1-> NULL
3. Но после вызова reverseList список Original становится: 1-> NULL

Это потому, что я иметь следующий код, чтобы перевернуть список:

 ListNode* reverseList(ListNode* head)
 {
     ListNode* temp = head;
     ListNode* temp1 = temp;
     ListNode* current = NULL, * nextNode = NULL;
     if (temp)
         current = temp->next;
     if (current)
         nextNode = current->next;
     while (current)
     {
         current->next = temp;
         temp = current;
         current = nextNode;
         if (current)
             nextNode = current->next;
     }
     temp1->next = NULL;
     return temp;
 }

Как только я выполню temp1->next = NULL в указанной выше функции reverseList (вторая последняя строка в функции), заголовок исходного списка изменен, и исходный список теперь указывает на 1-> NULL вместо 1-> 1-> 2-> 1-> NULL.

Ниже, если полный код, который вызывает функцию reverseList:

 struct ListNode
 {
     int val;
     ListNode* next;
     ListNode(int x):val(x),next(NULL){}
 };

 ListNode* reverseList(ListNode* head)
 {
     ListNode* temp = head;
     ListNode* temp1 = temp;
     ListNode* current = NULL, * nextNode = NULL;
     if (temp)
         current = temp->next;
     if (current)
         nextNode = current->next;
     while (current)
     {
         current->next = temp;
         temp = current;
         current = nextNode;
         if (current)
             nextNode = current->next;
     }
     temp1->next = NULL;
     return temp;
 }

 bool isPalindrome(ListNode* head) {
     //reverse the Linked list and then compare the two lists.
     if (head == NULL)
         return true;
     ListNode* head1 = head;
     ListNode* head2 = reverseList(head);
     while (head1 && head2)
     {
         if (head1->val != head2->val)
             return false;
         head1 = head1->next;
         head2 = head2->next;
     }
     return true;
 }

 int main()
 {
     ListNode* head = new ListNode(1);
     head->next = new ListNode(1);
     head->next->next = new ListNode(2);
     head->next->next->next = new ListNode(1);
     head->next->next->next->next = NULL;
     bool palindrome = isPalindrome(head);
     cout << palindrome << endl;
     return 0;
 }

Итак, когда функция reverseList возвращается, в функции isPalindrome происходит следующее:

1. head2 устанавливается на: 1->2->1->1->NULL
2. head и head1 установлены на 1->NULL

И я больше не могу сравнивать два связанных списка, чтобы проверить, являются ли они палиндромами друг друга (так как сравнение даст мне Результат).

Все это происходит потому, что я установил temp1->next=NULL в функции reverseList.

Знаете ли вы, как правильно завершить список в функции reverseList, чтобы она не влияла на исходный список?

Большое спасибо!

Answer 1

Ниже приведен исправленный код, в который я включил глубокую копию исходного списка (в функции isPalindrome):

 struct ListNode
 {
     int val;
     ListNode* next;
     ListNode(int x):val(x),next(NULL){}
 };

 ListNode* reverseList(ListNode* head)
 {
     ListNode* temp = head;
     ListNode* temp1 = temp;
     ListNode* current = NULL, * nextNode = NULL;
     if (temp)
         current = temp->next;
     if (current)
         nextNode = current->next;
     while (current)
     {
         current->next = temp;
         temp = current;
         current = nextNode;
         if (current)
             nextNode = current->next;
     }
     temp1->next = NULL;
     return temp;
 }

 bool isPalindrome(ListNode* head) {
     //reverse the Linked list and then compare the two lists.
     if (head == NULL)
         return true;
     ListNode* head1 = head;
     ListNode* temp1 = NULL, *temp2=NULL;
     bool firstEntry = true;

     //Deep Copy
     temp2 = temp1 = new ListNode(head1->val);
     while (head1->next)
     {
         temp1->next = new ListNode(head1->next->val);
         temp1 = temp1->next;
         head1 = head1->next;
     }

     temp1->next = NULL;
     ListNode* head2 = reverseList(head);
     while (temp2 && head2)
     {
         if (temp2->val != head2->val)
             return false;
         temp2 = temp2->next;
         head2 = head2->next;
     }
     return true;
 }

 int main()
 {
     ListNode* head = new ListNode(1);
     head->next = new ListNode(1);
     head->next->next = new ListNode(2);
     head->next->next->next = new ListNode(1);
     head->next->next->next->next = NULL;
     bool palindrome = isPalindrome(head);
     cout << palindrome << endl;
     return 0;
 }