Leetcode 每日一题——234. 回文链表

234. 回文链表

请判断一个链表是否为回文链表。

链表问题如果不涉及其他数据结构的话还是相对简单的，这道题很容易想到使用快慢指针，找到尾节点，翻转后半段链表，然后判断回文特性。具体C++的实现过程如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast!=NULL && fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        fast=NULL;
        while(slow)
        {
            ListNode *tmpnext=slow->next;
            slow->next=fast;
            fast=slow;
            slow=tmpnext;
        }
        while(fast && head)
        {
            if(fast->val!=head->val) return false;
            fast=fast->next;
            head=head->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

运行效果：

相同思路使用Python实现的代码如下：

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True
        slow=head
        fast=head
        while(fast and fast.next):
            slow=slow.next
            fast=fast.next.next
        tmp=None
        while(slow):
            tmpNext=slow.next
            slow.next=tmp
            tmp=slow
            slow=tmpNext
        fast=head

        while(fast and tmp):
            if(fast.val!=tmp.val):
                return False
            fast=fast.next
            tmp=tmp.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

运行效果：

来源：力扣（LeetCode）链接