[LinkedList]234. Palindrome Link

• 分类：LinkedList
• 时间复杂度: O(n)
• 空间复杂度: O(n)数组法/O(1)快慢指针

234. Palindrome Linked List

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

示例 1:

输入: 1->2  
输出: false  

示例 2:

输入: 1->2->2->1  
输出: true  

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码1: 转array，然后用2pointer做：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        if head==None or head.next==None:
            return True
        
        num_list = list()

        pointer = head
        while pointer!=None:
            num_list.append(pointer.val)
            pointer = pointer.next
        
        start = 0
        end = len(num_list)-1
        while(start<end):
            if num_list[start]!=num_list[end]:
                return False
            start+=1
            end-=1

        return True

代码2: 快慢指针，reverse后半段，然后和前半段对比：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverse(self, head):

        if head==None or head.next==None:
            return head
        
        res = None
        while head!=None:
            tmp = head.next
            head.next = res
            res = head
            head = tmp

        return res

    def isPalindrome(self, head: ListNode) -> bool:

        if head==None or head.next==None:
            return True
        
        fast = head
        slow = head
        
        while (fast.next!=None and fast.next.next!=None):
            fast = fast.next.next
            slow = slow.next

        reversed_slow = self.reverse(slow)
        while(reversed_slow!=None and head!=None):
            if reversed_slow.val!=head.val:
                return False
            reversed_slow=reversed_slow.next
            head=head.next

        return True

讨论：

1.看B站上的讲解学会的。如果还是不会，或者忘记了，请提醒自己看B站