題目描述

請(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)注明出處。

解題思路

# 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 is None or head.next is None :return True
        # 反轉(zhuǎn)鏈表 同時(shí)計(jì)數(shù)
        pre=ListNode(head.val) 
        print(pre.val)
        pre.next = None
        cur = head.next
        
        long = 1
        # print(cur)
        while cur :
            long += 1
            temp = cur.next
            phead = ListNode(cur.val)
            phead.next = pre
            pre = phead
            cur = temp

        k = (long+1)/2 
        while pre is not None and head is not None and k >= 0:
            print(pre.val,"---",head.val)
            if pre.val != head.val:
                print(pre.val,"---",head.val)
                return False
            pre = pre.next
            head = head.next
            k -= 1
        return True

總結(jié)

鏈表反轉(zhuǎn)