首页 > c/c++, LeetCode, 面试 > LeetCode面试题之回文单链表

LeetCode面试题之回文单链表

2016年7月15日 753 人阅读 发表评论 阅读评论

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
    CreateTime: 2016年6月16日17:50:20
    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:https://leetcode.com/problems/palindrome-linked-list/

分类: c/c++, LeetCode, 面试 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.