数据结构面试 之 回文单链表 附图解

1.限制与要求

• 时间复杂度O(n)，空间复杂度O(1)

2.思考

回文最初的概念是应用在字符串上的，比如"abccba"和“abcdcba”都是回文字符串。判断是否是回文字符串的算法也很简单，使用两个下标i、j，i从头开始向后遍历，j从尾开始向前遍历，只要i < j就一直遍历，在遍历过程中如果i和j位置上的字符不相同，则该字符串必然不是回文的并立即停止遍历，如果遍历结束后都没遇到不相同的字符，则该字符串是回文的。

• 单链表回文难点

• 我们无法像遍历连续空间那样，直接从尾部向前遍历。
• 即使解决了逆向遍历的问题，那么如何判断结束遍历也同样是个问题。

• 一个巧妙的解法

• 第一个问题：我们把单链表逆序然后再遍历就可以实现从尾部(逆序前的单链表)向前遍历了。
• 第二个问题：把链表先拆分成left和right两部分，然后只对right部分进行逆序。
• 最后我们从left头节点和逆序后的right头节点开始遍历，一直往后遍历直到链表尾。
• 遍历过程中出现不相同的数据则不是回文的单链表，否则就是回文的单链表。

3.算法图解

• 原链表进行拆分成左右两半

• 右半部分进行逆序

• 进行回文判断

4.代码实现

/*
    21 / 21 test cases passed.
    Status: Accepted
    Runtime: 28 ms
    Desc: 链表操作和思维的综合考察：
        1、对原链表进行拆分成左右两半
        2、对右半部分进行逆序
        3、进行回文判断
 */
#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode * getRight(ListNode * head)
    {
        int len = 1;
        ListNode * right = NULL;
        ListNode * cur = head;
        while (head->next != NULL)
        {
            ++len;
            head = head->next;
        }
        
        if (0 == len % 2) //偶数节点
        {
            len /= 2;
            --len;
            while (len--)
            {
                cur = cur->next;
            }
            right = cur->next; //保存右半链表的起始节点指针
            cur->next = NULL;  //这里断开
        }
        else //奇数节点
        {
            len /= 2;
            --len;
            while (len--)
            {
                cur = cur->next;
            }
            right = cur->next->next; //奇数节点要跳过中间节点
            cur->next->next = NULL;
            cur->next = NULL; //这里断开
        }
        
        return right;
    }
    
    ListNode * reverseList(ListNode * head)
    {
        ListNode * pre = NULL;
        ListNode * temp = head;
        ListNode * cur = head;
        
        while (cur != NULL)
        {
            cur = cur->next;
            temp->next = pre;
            pre = temp;
            temp = cur;
        }
        
        return pre;
    }
    
    bool isPalindrome(ListNode* head) {
        if (NULL == head) return true;
        if (NULL == head->next) return true;
        
        ListNode * left = head;
        ListNode * right = getRight(head); //对链表进行拆分，分成左右两端
        right = reverseList(right); //对右半部分链表进行逆序
        
        //判断是否是回文
        while (left)
        {
            if (left->val != right->val)
            {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        
        return true;
    }
};

5.OJ练习

LeetCode 回文单链表

6.相关题目

单链表逆序