CODEWITHSUNDEEP
c++
SSD
SSD

Reputation: 295

How to reverse a linked list without changing the original one in C++

I'm trying to test if a linked list is palindrome. To do this, I'm just going to reverse the linked list, and then check each node one by one in a loop. However, I don't know how to pass the original linked list by value. I think right now I'm passing the linked list by its reference, which modified the original structure after I reverse it.

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    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;
        }
        head = pre;
        return head;
    }
    bool isPalindrome(ListNode* head) {
        ListNode* original = head;
        ListNode* reverse = reverseList(head);// is there a way that I can pass it as a copy?

        while(original!=NULL){
            if(reverse->val == original->val){
                reverse=reverse->next;
                original=original->next;
            }else{
                return false;
            }

        }
        return true;

    }
};

Upvotes: 1

Views: 1913

Answers (1)

user8552182
user8552182

Reputation: 56

When you do this:

ListNode* original = head;

Your just copying the pointer which means you have two pointer variable pointing to the same area of memory so changing one will change the other. Could you not just de-reference the pointer and make a copy of that. You could then get a pointer to that new variable if need be. 

ListNode original = *head;
ListNode* original2 = &original;

You can then modify original2 without changing the head.

Upvotes: 1

Related Questions