路漫漫

john的博客

回文链表

发表于 更新于 分类于 ，
本文字数： 2.1k 阅读时长 ≈ 2 分钟

方案一

使用栈，将链表全部入栈，然后比较链表和栈顶，相同就出栈和链表向后移动
时间复杂度：O（n）
空间复杂度：O（n）

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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        
        ListNode* tmp = head;
        if (!tmp || !tmp->next) return true;

        //开辟一个栈
        stack<int> stackval;
        while (tmp)
        { 
            stackval.push(tmp->val);
            tmp = tmp->next;
        }

        //比较
        while (head)
        {
            if (head->val != stackval.top()) 
            {
                return false;               
            }
            stackval.pop();  
            head = head->next;
        }

        return true;
    }
};

在这里插入图片描述

方案二

压一半链表进栈，空间复杂度减半，需要遍历链表求长度，时间复杂度会增加
时间复杂度：O（n）
空间复杂度：O（n）

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
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* tmp = head;
        if (!tmp || !tmp->next) return true;

        int size = 0;   //保存链表的长度
        int middle = 0;
        stack<int> stk;

        //求链表的长度
        while (tmp)
        {
            ++size;
            tmp = tmp->next;
        }

        //入一半的栈
        middle = size / 2;
        tmp = head;
        int i = 1;
         while (tmp)
        { 
            if (i > middle)
            {
                stk.push(tmp->val);
            }
            
            tmp = tmp->next;
            i++;
        }

        //比较
        middle = size / 2;
        tmp = head;
        while (middle-- && tmp)
        {
            if (tmp->val != stk.top()) 
            {
                return false;               
            }
            stk.pop();  
            tmp = tmp->next;
        }

    return true;
    }
};

在这里插入图片描述

方案三

将链表的后半段反转，前后指针依次向后指，比较直到反转部分指针指向nullptr时停止
时间复杂度：O（n）
空间复杂度：O（1）

缺点：破坏了链表的结构

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
	//辅助函数，反转链表
    ListNode* listReverse(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nxt = nullptr;
        while (cur)
        {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

public:
    bool isPalindrome(ListNode* head) {
        if (!head|| !head->next) return true;

        //快慢指针找到链表的中间位置
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        //奇数情况
        if (fast != nullptr)
        {
            slow = slow->next;
        }

        //开始反转，从slow指针位置反转，包含slow位置
        slow = listReverse(slow);

        //开始比较
        fast = head;
        while (slow != nullptr){
            if (fast ->val != slow->val){
                return false;
            }
            fast = fast ->next;
            slow = slow->next;
        }

        return true;
    }
};

在这里插入图片描述

相关文章