Проверка, является ли связанный список палиндромным - PullRequest
Новая
       1

Проверка, является ли связанный список палиндромным

4 голосов
/ 10 ноября 2010

Рассмотрим связанный список, узлами которого являются символы, поэтому список представляет собой строку. Как вы пишете рекурсивную подпрограмму , чтобы проверить, является ли строка палиндромом, так что указанная функция начинает разматывать стек, когда обрабатывает символ (ы) в середине строки?

Например, предположим, что моя строка "мадам". Моя рекурсивная функция выглядит примерно так:

bool isPalin(const node *startnode, const node *currentnode, const node *midpoint, ...);

Когда currentnode->data == 'd', стек должен разматываться.

Мне задали этот вопрос для интервью; на данный момент я не могу думать о какой-либо пользе для этого вопроса, кроме как очень сложной загадкой.

Первые мысли: очень очевидный (хотя и не элегантный) способ:

  1. Сначала вычислить среднюю точку списка.
  2. Если currentnode «до» midpoint , вставьте устройство в стек вручную. Это можно решить, ведя счетчик.
  3. В противном случае, разматывайте поддерживаемый вручную стек на каждом шаге рекурсии и сравнивайте с текущим символом.

Есть идеи получше или свежие идеи?

Ответы [ 10 ]

9 голосов
/ 10 ноября 2010

Под "связанным списком" вы подразумеваете std::list? 

template <typename BiDiIterator>
bool isPalindrome(BiDiIterator first, BiDiIterator last) {
    if (first == last) return true;
    --last;
    if (first == last) return true;
    if (*first != *last) return false;
    return isPalindrome(++first, last); // tail recursion FTW
}

isPalindrome(mylist.begin(), mylist.end());

Я использовал тот факт, что можно итерировать как с конца, так и с начала. Неясно, задано ли это вопросом.

Используя односвязный список, вы можете запустить два итератора, один быстрый и один медленный. При каждом вызове увеличивайте один быстрый и медленный один раз. Когда быстрый достигает конца списка, медленный находится в средней точке (ит, +/- 1 с учетом списков нечетной и четной длины). В этот момент вернитесь из своей рекурсии, сравнивая значения символов. & Theta; (n) сложность для времени выполнения и использования памяти (не хвостовая рекурсия).

Я бы написал код, но пришло время спать здесь, в Великобритании.

[Редактировать: все утро 

template <typename FwdIterator>
std::pair<FwdIterator, bool> isPalindrome(FwdIterator slow, FwdIterator fast, FwdIterator last) {
    if (fast == last) return std::make_pair(slow, true);
    ++fast;
    if (fast == last) return std::make_pair(++slow, true);
    ++fast;
    FwdIterator next = slow;
    std::pair<FwdIterator, bool> result = isPalindrome(++next, fast, last);
    if (result.second == false) return result;
    if (*slow != *(result.first)) return std::make_pair(slow, false);
    ++(result.first);
    return result;
}

...

isPalindrome(mylist.begin(), mylist.begin(), mylist.end()).second;

Если по какой-то странной причине в вашем связанном списке нет итератора, то, надеюсь, эквивалентный код с if (fast->next == 0), fast = fast->next и т. Д. Очевиден. И, конечно, вы можете привести в порядок пользовательский интерфейс с помощью оболочки.

Я думаю, что вы можете избежать дополнительного хранилища, если вам разрешено временно изменять список, переворачивая список до «медленного» при спуске, а затем снова переворачивая его при подъеме. Таким образом, вам не нужно хранить копию slow в рекурсивном вызове: вместо этого вы можете вернуть дополнительный указатель для вызывающего абонента. Я не собираюсь беспокоиться.

] * * тысячу двадцать-один

4 голосов
/ 10 ноября 2010

Сложные по модулю детали, это легко.

Сначала найдите среднюю точку, вызывая рекурсивное перемещение одного указателя всего на один шаг, но на два других.Когда двухступенчатый указатель достигает конца, одношаговый указатель находится посередине.Непростая вещь: список четных и нечетных длин.

Затем выполните резервное копирование (возврат из рекурсивных вызовов) и, двигаясь назад, перемещайте среднюю точку на один шаг вперед для каждого возврата.Просто сравните содержимое этого узла с содержимым, доступным в качестве стандартного аргумента во время спуска.

Приветствия & hth.,

3 голосов
/ 10 ноября 2010

Если вам действительно хочется использовать стек, это обычное упражнение в теории вычислений с использованием недетерминированных автоматов.Идея состоит в том, чтобы поместить каждый символ в стек и на каждом символе ответвляться, причем одна ветвь пропускает символ (в случае, если это нечетный палиндром) и выталкивает каждый символ из стека, сравнивая его с одним в оставшейся части списка.другая ветвь делает то же самое, не пропуская этот начальный символ (в случае, если это четный палиндром), а третья продолжает добавлять элементы в стек (и рекурсивно начинает ветвление снова со следующего символа).Эти три ветви могут быть представлены путем передачи текущего состояния стека в каждую рекурсивно.

В псевдокоде: 

function isPalin(* start, * end, stack){
  if checkPalin(start, end, stack):
    return true;

  stack.push(*start);
  if checkPalin(start, end, stack):
    return true;

  if (start == end)
    return false;

  return isPalin(start.next, end, stack);
}

function checkPalin(* start, * end, stack){
  while (stack is not empty && start != end){
    start = start.next;
    if (*start != stack.pop())
      return false;
  }

  return (stack is empty && start == end);
}
1 голос
/ 26 декабря 2015
  1. Найти длину всей строки
  2. Получить узел, имеющий среднюю (среднюю) позицию
  3. Разбить список в этом узле
  4. Реверс первой половины

  5. Теперь сравните строку

    включает "stdafx.h"

    включает "LinkedList.h"

LinkedList :: LinkedList () { head = nullptr; count = 0; }

void LinkedList :: AddItem (char * data) { Узел узел = новый узел; node-> Data = (void ) malloc (strlen (data) + 1); 

strcpy((char*)node->Data, data);
node->Data = data;
node->Next = nullptr;
count++;

if(head == nullptr)
{
    head = node;        
    head->Next = nullptr;
    return;
}

Node *temp = head;

while(temp->Next!=nullptr)
{
    temp = temp->Next;
}

temp->Next = node;

}

void LinkedList :: TraverseList () { Узел * temp = head; 

while(temp !=nullptr)
{
    printf("%s \n", temp->Data);
    temp = temp->Next;
}

}

Node * LinkedList :: Reverse () { if (! head ||! (head-> Next)) { вернуть голову; } 

Node* temp = head;

Node* tempN = head->Next;

Node* prev = nullptr;

while(tempN)
{
    temp->Next = prev;

    prev= temp;
    temp = tempN;

    tempN = temp->Next;
}

temp->Next = prev;
head = temp;
return temp;

}

bool LinkedList :: IsPalindrome () { int len ​​= 0; Узел * temp = head; 

while(temp)
{
    len = len + strlen((char*)temp->Data);
    temp = temp->Next;
}

printf("total string length is %d \n", len);

int i =0;
int mid1 = 0;

temp = head;

while (i < len/2)
{
    int templen = strlen((char*)temp->Data);        

    if(i + strlen((char*)temp->Data) < (len /2))
    {
        i = i + strlen((char*)temp->Data);
        temp = temp->Next;
    }
    else
    {
        while(i < len/2)
        {
            mid1++;
            i++;
        }

        break;
    }
}

printf("len:%d, i:%d, mid1:%d mid2:%d \n",len, i, mid1, len-mid1);

Node* secondHalf = temp->Next;
temp->Next = nullptr;
Node *firstHalf = Reverse();

char* str1 = (char*)malloc(sizeof(char) * mid1 + 1);
char* str2 = (char*)malloc(sizeof(char) * mid1 + 1);

memcpy(str1, (char*)firstHalf->Data, mid1); 
str1[mid1] = '\0';

int slen = strlen((char*)temp->Data);

if(slen > mid1)
{
    memcpy(str2, (char*)firstHalf->Data + mid1, slen-mid1);
    str2[slen-mid1] = '\0';
}
else
{
    str2[0] = '\0';
}   

printf("%s, %s", str1, str2);
str1 = strrev(str1);

if(!*str2)
{
    str2 = (char*)secondHalf->Data;
    secondHalf = secondHalf->Next;
}

if(*str2 && len%2 == 1)
{
    str2++;
    if(!*str2)
    {
        str2 = (char*)secondHalf->Data;
        secondHalf = secondHalf->Next;
    }
}

while(*str1 && *str2)
{
    if(*str1 != *str2)
    {
        return false;
    }

    str1++;
    str2++;

    if(!*str1)
    {   
        retry:
        firstHalf = firstHalf->Next;
        if(firstHalf)
        {
            str1 = (char*) malloc(strlen((char*)firstHalf->Data) + 1);
            strcpy(str1,(char*)firstHalf->Data);                
            str1 = strrev(str1);
        }

        if(!*str1 && firstHalf)
        {
            goto retry;
        }
    }

    if(!*str2)
    {
        retrySecondHalf:
        temp = secondHalf;
        if(temp)
        {
            str2 = (char*)temp->Data;           
            secondHalf = secondHalf->Next;
        }

        if(!*str2 && secondHalf)
        {
            goto retrySecondHalf;
        }
    }
}

if(*str1 || *str2)
{
    return false;
}

return true;

}

int _tmain (int argc, _TCHAR * argv []) { LinkedList * list = new LinkedList (); 

list->AddItem("01234");
list->AddItem("");
list->AddItem("56");
list->AddItem("789");
list->AddItem("1"); 
list->AddItem("9");
list->AddItem("");
list->AddItem("876543210");

printf("Is pallindrome: %d \n", list->IsPalindrome());

return 0;

}

1 голос
/ 15 октября 2014

В Java это решение будет сравнивать уже прочитанную строку со строкой, которая приходит рекурсивно. Это не лучшее решение, так как даже когда это O (n), это S (n ^ 2), и он должен (как минимум) использовать StringBuffer для уменьшения всех конкатенаций.

Он использует класс-оболочку для передачи правой части строки вместе с логическим значением.

плюсы:

  1. только один проход в список, от головы до конца.
  2. не нужно заранее знать длину списка
  3. дополнительные структуры данных не нужны

минусы:

  1. использует много памяти S (n ^ 2)
  2. объединяет строки неэффективным образом
  3. рекурсивный раствор, медленный.

Код: 

boolean palindrome(Node n){
    RightSide v = palindromeRec(“”, n);
    return v.palindrome;
}

class RightSide{
    boolean palindrome;
    String right;
}

private RightSide palindromeRec(String read, Node n){
    RightSide v = new RightSide();

    if(n == null){
        v.palindrome = false;
        v.right = “”;
        return v;
    }

    v = palindromeRec(n.value + read, n.next);

    if(v.palindrome) 
        return v;
    else if(read.equals(v.right) || (n.value+read).equals(v.right)){
        v.palindrome = true;
        return v;
    }

    v.right = n.value + v.right;
    v.palindrome = false;

    return v;
}
1 голос
/ 27 февраля 2011

это то, что я спрашиваю, я думаю 

bool isPalindrom(node* head)
{
   if(!head) return true;

   node* left = head;
   node* mid = head;

   return cmp(left, mid, head);
}

bool cmp(node*& left, node*& mid, node* n)
{
   node* next = n->next;   

   if(next == 0)
   {
      node* lprev = left;
      left = left->next;
      return lprev->data == n->data;      
   }

   mid = mid->next;
   if(next->next == 0)
   {
      node* lprev = left;
      left = left->next->next;
      return lprev->data == next->data && lprev->next->data == n->data;
   }

   if(!cmp(left, mid, next->next)) return false;

   if(left == mid) return true;

   if(left->data != next->data) return false;

   left = left->next;

   if(left == mid) return true;

   if(left->data != n->data) return false;

   left = left->next;

   return true;
}
1 голос
/ 10 ноября 2010

Этот список связан дважды?Затем нужно передать начальный и конечный узлы, сравнить то, на что они указывают.Если они разные, верните false.Если они одинаковые, называйте себя рекурсивно с помощью start + 1 и end-1, пока start> end.

0 голосов
/ 28 марта 2013

Ниже приведен код рекурсии, где узел имеет данные в виде целого числа, просто замените его символом. Он выполняется за время O (n), использует постоянное пространство, отличное от неявного использования стека размера O (n). где n - количество узлов в связном списке. 

package linkedList;
class LinkedList {
    class LinkedListNode {
        public int data;
        public LinkedListNode next;
        public LinkedListNode (int d) {
            data = d;
            next = null;
        }
    }

    class PalinResult {
        public boolean done;
        public LinkedListNode forward;

        public PalinResult (LinkedListNode n) {
            forward = n;
            done = false;
        }
    }

    LinkedListNode root;

    public LinkedList () {
        root = null;
    }

    public LinkedListNode getRoot(){
        return root;
    }

    public boolean add(int d) {
        LinkedListNode t = new LinkedListNode (d);
        if (root == null) {
            root = t;
            return true;
        }

        LinkedListNode curr = root;
        while (curr.next != null) {
            curr = curr.next;
        }

        curr.next = t;
        return true;
    }

    /*
     * Takes O(n time)
     */
    public boolean checkPalindrome() {
        PalinResult res = new PalinResult (root);
        return     checkPalindromeRecur(root, res);
    }

    private boolean checkPalindromeRecur(LinkedListNode curr, PalinResult res) {
        if (curr == null) 
            return true;
        else {
            boolean ret = checkPalindromeRecur(curr.next, res);

            if (!ret || (res.done))
                return ret;

            if (curr == res.forward)
                res.done = true;

            if (curr.data == res.forward.data)
                ret = true;
            else
                ret = false;

            res.forward = res.forward.next;
            return ret;
        }
    }

    public static void main(String args[]){
        LinkedList l = new LinkedList();
        l.add(1);
        l.add(4);
        l.add(1);

        System.out.println(l.checkPalindrome());
    }
}
0 голосов
/ 02 ноября 2011

Итак (моя грубая идея - пожалуйста, дайте мне знать) Мы могли бы также

1) Рассчитать длину LL;
2) Правильно определить среднюю точку
// (для длины 5 средняя точка равна 3, но для длины 4 средняя точка равна 2).
3) Когда в средней точке - поверните LL от средней точки до конца LL;
4) Сравнивайте данные заголовка с новыми данными средней точки, пока ссылка на заголовок не будет повторена до середины, а новая ссылка с серединой повторяется до NULL

0 голосов
/ 10 ноября 2010

Для начала, перейдите к концу списка и сохраните указатель на последний узел как end.Затем сохраните указатель на первый узел как start.

Затем вызовите функцию и укажите эти значения.Функция будет:

  1. Проверить, если start == end (они указывают на одну и ту же ссылку).Если это так, он немедленно вернет истину.(Нечетное количество элементов в списке и средний элемент - единственный, что осталось.)
  2. Затем он будет смотреть на значения, представленные start и end.Если они не равны, он немедленно вернет false.(Не палиндром.)
  3. В противном случае он изменит start, чтобы указывать на следующую ссылку (предположительно start = start->next).
  4. Если start == end, немедленно вернуть true (обрабатываетрегистр для четного числа ссылок в списке).
  5. Найдите ссылку до end и задайте для нее end: link i = start; while (i->next != end) i = i->next; end = i;.
  6. Recurse, предоставляя новые значениядля start и end.
...