Thursday, July 16, 2015

LeetCode OJ - Palindrome Linked List

Problem:

Please find the problem here.

Solution:

Check Palindrome? Easy - copy it to an array, check if value matches using the array random access, linear time $ O(n) $! Apparently this is also the time lower bound. The key challenge here is constant space.

The key idea of not using extra space is to use existing space using a trick called pointer inversion. We use one pass to first determine the length. Then on the second pass, we walk to the middle and flip the pointers along the way so that we can go backwards, that allow us to go backwards - see an example to convince yourself how that works!

C stands for cursor, P stands for previous node

P = NULL
1->2->3->4->5->6->7->NULL
C

walk one step

NULL<-1<-P C->2->3->4->5->6->7

let's walk one more step

NULL<-1<-2<-P C->3->4->5->6->7

and so on!

Once we reach the center point we walk the left pointer and right pointer and match along the way, and fix up the inverted linked list!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/palindrome-linked-list/

#include "LEET_PALINDROME_LINKED_LIST.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

    class Solution
    {
    public:
        bool isPalindrome(ListNode* head)
        {
            unsigned int length = 0;
            ListNode* cursor = head;
            while (cursor != NULL)
            {
                cursor = cursor->next;
                length++;
            }
            if (length < 2)
            {
                return true;
            }

            int pointerWalkCount = length / 2; 
            cursor = head;
            ListNode* cursorPrev = NULL;
            for (int i = 0; i < pointerWalkCount; i++)
            {
                ListNode* next = cursor->next;
                cursor->next = cursorPrev;
                cursorPrev = cursor;
                cursor = next;
            }

            ListNode* left = cursorPrev;
            ListNode* leftNext = cursor;
            ListNode* right = cursor;
            if (length % 2 == 1)
            {
                right = right->next;
            }

            bool match = true;
            for (int i = 0; i < pointerWalkCount; i++)
            {
                match = match && (left->val == right->val);
                ListNode* leftPrev = left->next;
                left->next = leftNext;
                leftNext = left;
                left = leftPrev;
                right = right->next;
            }

            return match;
        }
    };

    void test(vector<int> data)
    {
        Solution solution;
        ListNode* head = NULL;
        ListNode* tail = NULL;
        for (unsigned int i = 0; i < data.size(); i++)
        {
            ListNode* newNode = new ListNode(data[i]);
            if (tail == NULL)
            {
                head = tail = newNode;
            }
            else
            {
                tail->next = newNode;
                tail = newNode;
            }
        }
        cout << solution.isPalindrome(head) << endl;
        ListNode* cursor = head;
        while (cursor != NULL)
        {
            ListNode* temp = cursor->next;
            delete cursor;
            cursor = temp;
        }
    }
};

using namespace _LEET_PALINDROME_LINKED_LIST;

int LEET_PALINDROME_LINKED_LIST()
{
    int case1[] = { 1, 2, 3 };
    int case2[] = { 1, 2, 2, 1 };
    test(vector<int>(case1, case1 + _countof(case1)));
    test(vector<int>(case2, case2 + _countof(case2)));
    return 0;
}

No comments :

Post a Comment