## Thursday, July 16, 2015

### LeetCode OJ - Palindrome Linked List

Problem:

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"

#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

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

int pointerWalkCount = length / 2;
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* tail = NULL;
for (unsigned int i = 0; i < data.size(); i++)
{
ListNode* newNode = new ListNode(data[i]);
if (tail == NULL)
{
}
else
{
tail->next = newNode;
tail = newNode;
}
}
while (cursor != NULL)
{
ListNode* temp = cursor->next;
delete cursor;
cursor = temp;
}
}
};

}