剑指 Offer II 027 回文链表

偶数个节点算法示意图：

反转后的回文链表：

可以观察到中间节点3为公共节点、null节点为公共节点，实际上把回文链表处理为两条相交链表。

奇数个节点算法示意图：

反转后的回文链表：

奇数个节点反转后，slow指针指向的单链表节点个数，少于fast指针指向的单链表。

方法1：vector容器存储

时间复杂度O(n)，空间复杂度O(n)

1. 声明vector容器list
2. for循环：声明指针ptr指向头节点head->next；ptr!=nullptr；ptr=ptr->next
3. ptr每次移动一个节点，取当前节点的值存储在list中
4. for循环：声明指针ptr1，ptr2指向数组的头和尾；ptr1的下标小于ptr2；ptr1向后移动一个，ptr2向前移动一个
5. 如果ptr1指向的值 !=ptr2指向的值，返回false
6. 返回true

class Solution {
public:
    bool isPalindrome(ListNode* head) {
    vector<int> list;
    for(ListNode* ptr=head;ptr;ptr=ptr->next)
    {
        list.emplace_back(ptr->val);
    }
    for(int i=0,j=list.size()-1;i<j;i++,j--)
    {
        if(list[i]!=list[j]) return false;
    }
    return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法2：双指针

时间复杂度O(n)，空间复杂度O(1)

1. 声明三个指针指向头结点
2. 循环：移动指针
3. 快指针每次走两个节点，慢指针每次走一个节点
4. 如果快指针或快指针的下一个为空，退出循环
5. 快指针移动到慢指针的位置
6. 慢指针赋值为空指针
7. 循环：
8. 声明一个temp节点存储快指针的下一个节点
9. 快指针的下一个节点为慢指针
10. 慢指针移动到快指针的位置
11. 快指针移动到temp节点的位置
12. 直到快指针为空，退出循环
13. (此时慢指针指向反转链表的头结点) 快指针移动到头结点
14. 循环：
15. 慢指针每次移动一个，快指针每次移动一个
16. 如果慢指针的值!=快指针的值，返回false
17. (奇数个节点时慢指针所指链表节点个数少1)如果慢指针==nullptr，返回true

/**
 * 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) {
        if(!head) return false;
        ListNode* slowptr = head;
        ListNode* fastptr = head;

        while(fastptr&&fastptr->next)
        {
            if(!fastptr->next) break;
            fastptr=fastptr->next->next;
            slowptr=slowptr->next;
        }
        fastptr=slowptr;
        slowptr=nullptr;

        while(fastptr)
        {
            ListNode* temp=fastptr->next;
            fastptr->next=slowptr;
            slowptr=fastptr;
            fastptr=temp;
        }
        fastptr=head;

        while(fastptr&&slowptr)
        {
            if(slowptr->val!=fastptr->val) return false;
            slowptr=slowptr->next;
            fastptr=fastptr->next;
        }
        return true;
    }
};
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

打印公共节点的代码：

测试用例：[1,2,3,2,1]，输出：3为公共节点空节点为公共节点

while(slowptr)
{
    if(slowptr->val!=fastptr->val) return false;
    if(slowptr==fastptr&&fastptr->val==3) cout<<"3为公共节点";
    slowptr=slowptr->next;
    fastptr=fastptr->next;
}
if(slowptr==fastptr&&fastptr==nullptr) cout<<"空节点为公共节点";
1
2
3
4
5
6
7
8