Day83 | 灵神 | 快慢指针 回文链表

234.回文链表

234. 回文链表 - 力扣（LeetCode）

思路：

昨天虽然重排链表没想出来

但是有了昨天的思路，这道题的思路立马就显而易见了

找中间节点然后翻转后半段，然后一个一个对比，不一样就返回false，退出循环就是true

不过毕竟是个easy题目，也不必这么麻烦，就是把链表值复制到数组然后去前后分别遍历就完事了

完整代码：

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
class Solution {
public:
    //876.链表的中间节点
    ListNode* middleNode(ListNode* head) {
        ListNode *l=head;
        ListNode *r=head;
        while(r!=nullptr&&r->next!=nullptr)
        {
            l=l->next;
            r=r->next->next;
        }
        return l;
    }
    //206.反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode *p=head;
        ListNode *pre=nullptr;
        while(p!=nullptr)
        {
            ListNode* q=p->next;
            p->next=pre;
            pre=p;
            p=q;
        }
        return pre;
    }
    void reorderList(ListNode* head) {
        ListNode *mid=middleNode(head);
        ListNode *head2=reverseList(mid);
        while(head2->next)
        {
            ListNode* ntx1=head->next;
            ListNode *ntx2=head2->next;
            head->next=head2;
            head2->next=ntx1;
            head=ntx1;
            head2=ntx2;
        }
    }   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//更为简单的方法
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};