Featured image of post palindromeLinkedList

palindromeLinkedList

234. 回文链表

分析

  1. 计算链表长度

    • 遍历链表一次,统计节点总数 len。用于确定需要存入栈的节点数量
  2. 存储前半部分元素到栈中

    • 再次遍历链表,将前半部分的节点值压入栈中。如果链表长度为奇数,则跳过中间节点(因为中间节点不影响回文判断)
  3. 比较后半部分的值

    • 从链表中间位置开始继续遍历链表,每遇到一个节点,就弹出栈顶的元素,与当前节点值比较。如果有任意不相等的情况,说明链表不是回文链表
  4. 判断结果

    • 遍历完后,若所有值都匹配,则链表是回文的,返回 true

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
public:
    bool isPalindrome(ListNode* head)
    {
        // 求链表长度
        int len = 0;
        for (ListNode* p = head; p; p = p->next)
            ++len;

        // 用栈存储前半部分节点值
        ListNode* p = head;
        std::stack<int> stk;
        for (int i = 0; i < len / 2; ++i)
        {
            stk.push(p->val);
            p = p->next;
        }

        // 如果链表长度为奇数,跳过中间节点
        if (len % 2 == 1)
            p = p->next;

        // 比较后半部分节点值与栈中元素
        while (p)
        {
            if (stk.top() != p->val)
                return false;
            stk.pop();
            p = p->next;
        }

        return true;
    }
};
Built with Hugo
Theme Stack designed by Jimmy