回文问题

背景简介

若一个字符串的正序与倒序相同，则称其为回文字符串。比如”level”或者”noon”等都是回文字符串。

问题描述

判断一个字符串是否是回文字符串。
如果字符串通过数组存储，通过下标运算能够轻易得到结果。
若考虑字符串是通过单链表来存储，那该如何来判断是一个回文串呢？

解法

1. 快慢指针定位中间节点；
2. 从中间节点对后半部分逆序；
3. 前后半部分进行比较，判断是否为回文串。

代码

python

import sys

class Node(object):
    '''
    构造节点
    '''
    def __init__(self, value):
        self.value = value
        self.next = None

def create_link_list(str):
    '''
    将字符串存储在单链表中
    '''
    head = Node(str[0])
    cur = head
    for i in range(1, len(str)):
        node = Node(str[i])
        cur.next = node
        cur = cur.next

    return head

def reverse(node):
    '''
    翻转链表
    '''
    if not node.next:
        return node

    head = node
    pre = node
    node = pre.next
    while node:
        tmp = node.next
        node.next = pre
        pre = node
        node = tmp

    head.next = None
    return pre

def is_palindrome(str):
    '''
    判断是否为回文串
    '''
    flag = True
    node = create_link_list(str)
    slow = node
    fast = node

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    reverse_node = reverse(slow)
    while node and reverse_node:
        if node.value == reverse_node.value:
            node = node.next
            reverse_node = reverse_node.next
        else:
            flag = False
            break

    return flag

if __name__ == '__main__':
    str = sys.argv[1]
    print(is_palindrome(str))

运行结果：

(.venv) ➜  回文问题 git:(master) ✗ python palindrome.py 12412
False
(.venv) ➜  回文问题 git:(master) ✗ python palindrome.py 12421
True
(.venv) ➜  回文问题 git:(master) ✗ python palindrome.py 4
True
(.venv) ➜  回文问题 git:(master) ✗ python palindrome.py 1212
False
(.venv) ➜  回文问题 git:(master) ✗ python palindrome.py 1221
True

c++

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

typedef struct _LinkNode {
    char value;
    struct _LinkNode *next = NULL;
} LinkNode;

LinkNode* createNodeList(string palindrome) {
    LinkNode* head = NULL;
    LinkNode* cur = NULL;

    head = (LinkNode*)malloc(sizeof(LinkNode));
    head->value = palindrome[0];
    cur = head;

    for (int i=1; i<palindrome.length(); i++) {
        LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
        node->value = palindrome[i];
        cur->next = node;
        cur = node;
    }

    return head;
}

LinkNode* reverseNodeList(LinkNode* node) {
    if (!node || !node->next) {
        return node;
    }

    LinkNode* pre = NULL;
    LinkNode* next = NULL;

    while (node) {
        next = node->next;
        node->next = pre;
        pre = node;
        node = next;
    };

    return pre;
}

bool isPalindrome(string palindrome) {
    bool is_palindrome = true;
    LinkNode* node = createNodeList(palindrome);
    LinkNode* slow = NULL;
    LinkNode* fast = NULL;

    slow = fast = node;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    LinkNode* reverse_node = reverseNodeList(slow);

    while (node && reverse_node) {
        if (node->value == reverse_node->value) {
            node = node->next;
            reverse_node = reverse_node->next;
        } else {
            is_palindrome = false;
            break;
        }
    }

    return is_palindrome;
}

int main(int argc, char *argv[]) {
    string str = argv[1];
    bool flag = isPalindrome(str);
    if (flag) {
        cout << str << "是回文字符串" << endl;
    } else {
        cout << str << "不是回文字符串" << endl;
    }

    return 0;
}

运行结果:

[root@mail ~]# ./palindrome 12412
12412不是回文字符串
[root@mail ~]# ./palindrome 12421
12421是回文字符串
[root@mail ~]# ./palindrome 4
4是回文字符串
[root@mail ~]# ./palindrome 1212
1212不是回文字符串
[root@mail ~]# ./palindrome 1221
1221是回文字符串