C++中不修改原链表实现反转及链表回文判断的方法

Hey there! Let's fix that issue you're having with your palindrome check for singly linked lists.

The core problem here is that when you pass head to reverseList, even though we're passing the pointer by value, the pointer still points to the same underlying nodes as the original list. So when you modify the next pointers of those nodes in the reverse function, you're actually altering the original list's structure—this is why your comparison logic was broken (you ended up comparing a partially reversed original list to itself, not the original vs reversed copy).

To fix this, you need to create a full copy of the original linked list first, then reverse that copy instead of the original. This way, the original list remains untouched while you do your comparison.

Step-by-Step Fix: #

1. Add a helper function to copy the linked list: This will create entirely new nodes with the same values as the original, so reversing the copy won't affect the original list at all.
2. Modify your isPalindrome function: Use the copy instead of the original when calling reverseList.
3. Handle memory cleanup: Since we're creating new nodes in C++, we should delete them after the check to avoid memory leaks (optional for online judges, but good practice).

Here's the updated code with these changes:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // Helper function to reverse a linked list
    ListNode* reverseList(ListNode* head) {
        if(!head) return NULL;
        ListNode* current = head;
        ListNode* pre = NULL;
        ListNode* nextTemp = NULL;
        while(current!=NULL) {
            nextTemp = current->next;
            current->next = pre;
            pre = current;
            current = nextTemp;
        }
        return pre;
    }

    // Helper function to create a full copy of a linked list
    ListNode* copyList(ListNode* head) {
        if (!head) return nullptr;
        // Create the first node of the copy
        ListNode* newHead = new ListNode(head->val);
        ListNode* copyCurr = newHead;
        ListNode* originalCurr = head->next;
        
        // Traverse original list and copy each node
        while (originalCurr != nullptr) {
            copyCurr->next = new ListNode(originalCurr->val);
            copyCurr = copyCurr->next;
            originalCurr = originalCurr->next;
        }
        return newHead;
    }

    bool isPalindrome(ListNode* head) {
        // Edge cases: empty list or single node is always a palindrome
        if (!head || !head->next) return true;

        ListNode* original = head;
        ListNode* copiedList = copyList(head); // Copy original list
        ListNode* reversedCopy = reverseList(copiedList); // Reverse the copy, not original

        // Compare original and reversed copy
        while (original != nullptr) {
            if (original->val != reversedCopy->val) {
                // Clean up copied list before returning
                cleanupList(copiedList);
                return false;
            }
            original = original->next;
            reversedCopy = reversedCopy->next;
        }

        // Clean up copied list after successful check
        cleanupList(copiedList);
        return true;
    }

    // Helper to clean up memory for the copied list
    void cleanupList(ListNode* head) {
        ListNode* temp;
        while (head != nullptr) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

Key Explanations: #

• copyList: Creates new nodes for every element in the original list, so the copy lives in separate memory space. Reversing this copy won't touch the original list's nodes.
• Memory Cleanup: The cleanupList function ensures we don't leave orphaned nodes hanging around, which is important for real-world C++ applications (though some online judges like LeetCode will handle this automatically).
• Edge Cases: We added checks for empty lists or single-node lists, which are trivial palindromes and save unnecessary computation.

Bonus Optimization (Optional): #

If you want to avoid using O(n) extra space (from copying the list), you can use a fast-slow pointer technique to find the midpoint of the list, reverse the second half, compare it to the first half, then reverse the second half back to restore the original list. This brings the space complexity down to O(1), though it's a bit more involved. Let me know if you want details on that approach!

内容的提问来源于stack exchange，提问作者SSD