A basic method to solve the linked-list problem C++ implementation


  • 1

    We find many Middle Hard problem in the leetcode, in fact the linked-list problem is one of the most typical

    problem set we need to solve.

    One of the basic operation of the linked-list we need to grasp is to quickly implement the

      reverse-linked-list
    

    use "pre node" and "next node" to finish all the reverse-related tasks

    Here is the C++ implementation:

    ListNode* reverseList(ListNode* head){
        ListNode* pre=NULL;
        ListNode* next=NULL;
        while(head!=NULL){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
    

    Based on the reverse-basic operation, next we just to find the middle node and reverse the first half or the

    second half.

    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)    return true;
        ListNode * dummy=new ListNode(-1); dummy->next=head;
        ListNode *slow=dummy, *fast=dummy;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        slow->next=reverseList(slow->next);
        slow=slow->next;
        while(slow!=NULL){
            if(head->val!=slow->val)    return false;
            head=head->next;
            slow=slow->next;
        }
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.