1. Problem Description
This is a
a Microsoft interview question for software developer engineer from careercup. Here is the original thread,
"
Given a singly connected linked list, find the largest palindrome in the list in O(1) space.
- neer.1304 9 days ago in United States | Report Duplicate | Flag ".
2. Algorithm
This is a more difficult question than
Data Structure and Algorithm - Linked List: Palindrome and
Data Structure and Algorithm - Linked List: Palindrome II, which require to use O(1) space to find out if a linked list is a palindrome. In order to achieve O(1) space the technique of splitting the linked list is still applicable for this question as well.
Pseudo-code:
- Initialize
startPtr as
nullptr - points to the starting node of palindrome
- Initialize
len as the length of palindrome of 0
- Return empty
startPtr and zero
len, if linked list is empty
- Point
startPtr to head and initialize
len as 1
- Split the linked list as two equal parts and count the size
* If linked list has even number of nodes as
S, then
>
middleNode point to the (
S/2)th node
>
firstHalfCount as
S/2 and totalCount as
S
* If odd number of node(s), then
>
middleNode points to (
S/2+1)th node
>
firstHalfCount as
S/2+1 and totalCount as
S
- Reverse the 1st half linked list and keep the 2nd half as
firstHalfHead,
secondHalfHead
- If potential maximal palindrome size is greater than
len
(2*firstHalfCount + 1) > len, and
firstHalfHead and
secondHalfHead are valid, then
- Compare
firstHalfHead and
secondHalfHead until the first difference appearing
- The
length is greater than
len
> Point
startPtr to the last node of
firstHalfHead that have the same value in both
> Update
len as the current
length
- Compare
firstHalfHead and
secondHalfHead->next until the first difference appears
- If the
length+1 is greater than
len
> Point
startPtr to the last node of
firstHalfHead that have the same value in both
> Update
len as the current
length+1
- Update:
>
firstHalfCount =
firstHalfCount -
1;
> Push front the head of
firstHalfHead to
secondHalfHead
> Point
firstHalfHead into its next
- Keep loop this step until any of the condition does not hold
- Recover the linked list
- Split the linked list into two again and count the size
- Reverse the 1st half and keep the 2nd half as
firstHalfHead and
secondHalfHead
- Assign
secondHalfCount =
totalCount -
firstHalfCount
- If potential maximal palindrome size is greater than
len,
(2*secondHalfCount + 1) > len, and
firstHalfHead and
secondHalfHead are valid, then
- Compare
firstHalfHead and
secondHalfHead until the first difference appearing
- If the
length is greater than
len
> Point
startPtr to the last node of
firstHalfHead that have the same value in both
> Update
len as the current
length
- Compare
firstHalfHead->next with
secondHalfHead until the first difference appears
- If the
length+1 is greater than
len
> Point
startPtr to the last node of
firstHalfHead that have the same value in both
> Update
len as the current
length+1
- Update:
>
secondHalfCount =
secondHalfCount - 1
> Push front the head of
secondHalfHead to
firstHalfHead
> Point
secondHalfHead into its next
- Keep loop this step until any of the condition does not hold
- Recover the linked list
- Return
startPtr and
len
3. C++ Solution
// ********************************************************************************
// Implementation
// ********************************************************************************
#pragma once
#include "LinkedListAlgo.h"
#include "LinkedListElement.h"
#include <vector>
#include <cassert>
template<typename T>
class LinkedListLongestPalindrome
{
public:
LinkedListLongestPalindrome() = default;
LinkedListLongestPalindrome(LinkedListLongestPalindrome&) = delete;
LinkedListLongestPalindrome(LinkedListLongestPalindrome&&) = delete;
LinkedListLongestPalindrome& operator=(LinkedListLongestPalindrome&) = delete;
LinkedListLongestPalindrome& operator=(LinkedListLongestPalindrome&&) = delete;
~LinkedListLongestPalindrome() = default;
struct LL_PalindromeResult
{
LL_PalindromeResult()
: LL_PalindromeResult(nullptr, 0)
{}
LL_PalindromeResult(LinkedListElement<T> *ptr, size_t l)
: startPtr(ptr), len(l)
{
}
LL_PalindromeResult(LL_PalindromeResult&) = default;
~LL_PalindromeResult() = default;
LinkedListElement<T> *startPtr;
size_t len;
};
LL_PalindromeResult operator()(LinkedListElement<T>* head)
{
LL_PalindromeResult result;
if (head == nullptr) {
return result;
}
result = LL_PalindromeResult(head, 1);
if (head->next == nullptr) {
return result;
}
// find the middle node
LinkedListElement<T> *middleNode;
size_t firstHalfCount;
size_t totalCount;
SplitLinkedListIntoTwo(head, middleNode, firstHalfCount, totalCount);
// split the node
LinkedListElement<T> *firstHalf;
LinkedListElement<T> *secondHalf;
SplitAndReverseTheFirstHalf(head, middleNode, firstHalf, secondHalf);
// find the longest palindrome in the 1st run
LL_PalindromeResult tempResult = FindLongestPalindrome(firstHalf,
secondHalf,
result.len,
firstHalfCount,
false);
if (tempResult.len > result.len) {
result = tempResult;
}
// recover the linked list
RecoverFromSplitting(firstHalf, secondHalf);
assert(firstHalf == head);
// split the node again
SplitAndReverseTheFirstHalf(head, middleNode, firstHalf, secondHalf);
// find the longest palindrome in the 2nd run
tempResult = FindLongestPalindrome(firstHalf,
secondHalf,
result.len,
totalCount - firstHalfCount,
true);
if (tempResult.len > result.len) {
result = tempResult;
}
// recover the linked list
RecoverFromSplitting(firstHalf, secondHalf);
return result;
}
private:
LL_PalindromeResult FindLongestPalindrome(LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf,
size_t curMax,
size_t halfCount,
bool reversed)
{
LinkedListElement<T> *temp;
LL_PalindromeResult result(nullptr, curMax);
LL_PalindromeResult tempResult;
while ((halfCount * 2 + 1) > result.len && firstHalf != nullptr && secondHalf != nullptr) {
tempResult = GetCommon(firstHalf, secondHalf, reversed);
// track the longest palindrome
if (tempResult.len > result.len) {
result = tempResult;
}
// update the node and count for the next loop
if (reversed) {
temp = secondHalf->next;
secondHalf->next = firstHalf;
firstHalf = secondHalf;
secondHalf = temp;
}
else {
temp = firstHalf->next;
firstHalf->next = secondHalf;
secondHalf = firstHalf;
firstHalf = temp;
}
--halfCount;
}
return result;
}
LL_PalindromeResult GetCommon(LinkedListElement<T> *x,
LinkedListElement<T> *y,
bool reversed)
{
if (x == nullptr || y == nullptr) {
return LL_PalindromeResult();
}
// compare firstHalf with secondHalf
LL_PalindromeResult result1 = CompareCommon(x, y, 0);
// depends on which run
// - compare firstHalf->next with secondHalf
// - compare firstHalf with secondHalf->next
LL_PalindromeResult result2 = reversed ?
CompareCommon(x->next, y, 1) : CompareCommon(x, y->next, 1);
// return the longer palindrome
return result1.len > result2.len ? result1 : result2;
}
LL_PalindromeResult CompareCommon(LinkedListElement<T> *x,
LinkedListElement<T> *y,
size_t curLongestLen)
{
// compare two nodes until the first diverge appears
LL_PalindromeResult result(nullptr, curLongestLen);
while (x != nullptr && y != nullptr) {
if (x->data == y->data) {
result.len += 2;
result.startPtr = x;
x = x->next;
y = y->next;
}
else {
break;
}
}
return result;
}
void SplitLinkedListIntoTwo(LinkedListElement<T>* head,
LinkedListElement<T>* &middleNode,
size_t &firstHalfCount,
size_t &totalCount)
{
if (head == nullptr) {
middleNode = nullptr;
firstHalfCount = totalCount = 0;
return;
}
// a, b, c, d, e, f, g, h
// a, a
// b, c
// c, e
// d, g
// d, nullptr
// a, b, c, d, e, f, g, h, i
// a, a
// b, c
// c, e
// d, g
// e, i
// e, nullptr
LinkedListElement<T> *slowPtr = head;
{
LinkedListElement<T> *fasterX2 = head;
while (fasterX2 != nullptr) {
if (fasterX2->next != nullptr) {
++totalCount;
fasterX2 = fasterX2->next;
if (fasterX2->next != nullptr) {
++totalCount;
++firstHalfCount;
slowPtr = slowPtr->next;
}
}
fasterX2 = fasterX2->next;
}
}
middleNode = slowPtr;
}
void SplitAndReverseTheFirstHalf(LinkedListElement<T> *head,
LinkedListElement<T> *middleNode,
LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf)
{
if (middleNode == nullptr) {
firstHalf = secondHalf = nullptr;
return;
}
secondHalf = middleNode->next;
middleNode->next = nullptr;
firstHalf = head;
LL_Reverse(&firstHalf);
}
void RecoverFromSplitting(LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf)
{
LinkedListElement<T>* temp;
if (firstHalf != nullptr) {
temp = firstHalf;
LL_Reverse(&firstHalf);
temp->next = secondHalf;
}
else {
firstHalf = secondHalf;
}
}
};
// ********************************************************************************
// Test
// ********************************************************************************
void TestLinkedListLongestPalindrome()
{
using Result = LinkedListLongestPalindrome<char>::LL_PalindromeResult;
{
LinkedListElement<char> *inputLL = nullptr;
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 0);
assert(r.startPtr == nullptr);
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'B');
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("ABCDEFGHIJKLMN");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("AAAAAAAAAAAAAAAAAAAAA");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == input);
}
{
const std::string input("ABABCDEFGFEDCBAXY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("ABABCDEFGFEDCBAXYZUVWXYZ");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("UVWXYZABABCDEFGFEDCBAXYZ");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("AB01234567899876543210XY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("asfdasdfasAB01234567899876543210XY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210XYkljfkajsdkfasd");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210ABCDDCBAxyx");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
}
