1.题目描述：
Category Difficulty Likes Dislikes
algorithms Easy (48.61%) 1048 -
Tags
Companies
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
2.分析
这个问题首先思考到的快慢指针，因为是链表，所以操作没有数组那么方便，所以可以将所有的val放到一个数组里，但是这样会导致空间复杂度为O(n)。
3.解决
- 快慢指针
#
# @lc app=leetcode.cn id=234 lang=python3
#
# [234] 回文链表
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
"""
快慢指针法 时间复杂度为O(n), 空间复杂度为O(n)
"""
if not head or head.next == None:
return True
target_list = list()
while head:
target_list.append(head.val)
head = head.next
slow_point, fast_point = 0, len(target_list) - 1
while slow_point <= fast_point:
if target_list[slow_point] != target_list[fast_point]:
return False
else:
slow_point += 1
fast_point -= 1
return True
采用pop方式
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums)
j = 0
for i in range(length):
if nums[i] == 0:
nums.append(0)
j += 1
i = 0
while j:
if nums[i] == 0:
nums.pop(i)
j -= 1
else:
i += 1
