234. 回文链表

难度：简单

题目

请判断一个链表是否为回文链表。

示例 1：

输入: 1->2
输出: false

示例 2：

输入: 1->2->2->1
输出: true

进阶：

你能否用\(O(n)\)时间复杂度和\(O(1)\)空间复杂度解决此题？

Reference

题解

基本思路： 反序构建一个新的链表，比较两个链表是否相同

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getNode(int val, struct ListNode *next)
{
    struct ListNode *ret = (struct ListNode *)malloc(sizeof(struct ListNode));
    ret->val = val;
    ret->next = next;
    return ret;
}

bool isPalindrome(struct ListNode* head){
    int len = 0;
    struct ListNode *reversed = NULL, *cur1 = head, *cur2 = NULL;
    while(cur1 != NULL)
    {
        reversed = getNode(cur1->val, reversed);
        cur1 = cur1->next;
        len++;
    }
    cur1 = head;
    cur2 = reversed;
    for (int i = 0; i < len / 2; i++)
    {
        if (cur1->val != cur2->val)
            return false;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return true;
}

评论