leetcode hot100 之 回文链表

题目

给定一个链表，请判断其是否是回文链表。

输入：head = [1,2,2,1]
输出：true

原题链接：https://leetcode.cn/problems/palindrome-linked-list/

思路 思路1

首先计算链表的长度，这样便于把链表分为两半。
一个不用改变原链表的方式，就是借用栈，将前半部分入栈。再遍历后半部分，同时不断出栈和相应的节点对比即可。这种方法好处是不用改变原链表，但是会有额外空间开销。

这里可以更极致一点优化，其实找中间节点时，可以通过快慢指针来实现。而不是先遍历一遍计算长度。

• 复杂度分析
  • 时间复杂度 O(n)。
  • 空间复杂度 O(n)。

思路2

如果不想有额外的空间开销，则需要改变原链表，如将后半部分进行反转，再将前后两部分逐一比较。

• 复杂度分析
  • 时间复杂度 O(n)。
  • 空间复杂度 O(1)。

代码 代码1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0;
        ListNode* temp = head;
        while(temp) {
            n++;
            temp = temp->next;
        }
        int m = n / 2;
        ListNode* cur = head;
        stack<ListNode*> node_stack;
        while(m > 0) {
            m--;
            node_stack.push(cur);
            cur = cur->next;
        }
        // 长度为奇数时，跳过最中间的节点
        if (n % 2 == 1) {
            cur = cur->next;
        }
        while (cur) {
            ListNode* prev = node_stack.top();
            if (cur->val != prev->val) {
                return false;
            }
            node_stack.pop();
            cur = cur->next;
        }
        return true;
    }
};

代码2

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return true;
        }
        int n = 0;
        ListNode* temp = head;
        while(temp) {
            temp = temp->next;
            n++;
        }
        temp = head;
        int m = n / 2;
        while (m > 0) {
            temp = temp->next;
            m--;
        }
        if (n % 2 == 1) {
            temp = temp->next;
        }   
        ListNode* prev = temp;
        ListNode* cur = temp->next;
        prev->next = NULL; //必须加这句，不知道为啥，否则cur->next 不能指向 prev，不能形成回环
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        m = n / 2;
        while (m > 0) {
            if (prev->val != head->val) {
                return false;
            }
            head = head->next;
            prev = prev->next;
            m--;
        }
        return true;
    }
};