I am looking at LeetCode problem 234. Palindrome Linked List:

Given the head of a singly linked list, return true if it is a palindrome.

I first made a function that'll return the reversed linked list, and then I checked it with the original list.

This is my code:

class Solution {
public:
    
    ListNode* reverse(ListNode* head)
    {
        if(head==NULL||head->next==NULL)
            return head;
        
        ListNode* rest=reverse(head->next);
        head->next->next=head;
        head->next=NULL;
        
        return rest;
    }
    
    
    bool isPalindrome(ListNode* head)
    {
        ListNode* p=head;
        ListNode* node2=reverse(p);  
        
        while(head!=NULL && node2!=NULL)
        {
            if(head->val!=node2->val)
                return false;
          
            
            head=head->next;
            node2=node2->next;
        }
        
        return true;
    }
};

But it is returning true in cases where it should return false, like for 1->1->2->1.

Where am I going wrong with this?

CodePudding user response：

After these statements

ListNode* p=head;
ListNode* node2=reverse(p);

the original list is broken. That is if the initial list is not empty then after calling the member function reverse head->next is equal to nullptr.

CodePudding user response：

reverse will mutate the only list you have, so after the reversal, head points to the tail of the list. Its next member has been set to nullptr. You cannot expect to move two pointers in opposite directions along one and the same singly linked list. There is only one direction possible.

^{(Side note: in C don't use NULL for pointers, but nullptr).}

The naive solution is to create a new, second list that is the reversal of the original list, without changing anything to the original list. Then the while loop will work as you expected it. The downside of such a solution is that it needs to duplicate each node -- requiring O(n) auxiliary space.

A bit smarter is to split the original list into two halves, and reverse only the second of these two. Then again, the loop will work.

And, when avoiding the O(n) auxiliary space, you should also make the reverse function iterative instead of recursive, as the recursive version uses O(n) stack space.

Have a go at it.

I provide here a spoiler solution:

class Solution { private: ListNode* reverse(ListNode* head) { ListNode* prev = nullptr; ListNode* current = head; ListNode* temp; while (current) { temp = current->next; current->next = prev; prev = current; current = temp; } return prev; } ListNode* mid(ListNode* head) { ListNode* mid = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { mid = mid->next; fast = fast->next->next; } return mid; } bool compareCommon(ListNode* head, ListNode* head2) { while (head != nullptr && head2 != nullptr) { if (head->val != head2->val) return false; head = head->next; head2 = head2->next; } return true; } public: bool isPalindrome(ListNode* head) { return compareCommon(head, reverse(mid(head))); } };