• 分類：LinkedList
• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(n)數(shù)組法/O(1)快慢指針

234. Palindrome Linked List

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

示例 1:

輸入: 1->2  
輸出: false  

示例 2:

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

進(jìn)階： 你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/palindrome-linked-list 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

代碼1: 轉(zhuǎn)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后半段，然后和前半段對(duì)比：

# 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站上的講解學(xué)會(huì)的。如果還是不會(huì)，或者忘記了，請(qǐng)?zhí)嵝炎约嚎碆站