Grind75第4天 | 141.环形链表、876.链表的中间节点、125.验证回文串

141.环形链表

题目链接：https://leetcode.com/problems/linked-list-cycle

解法：

使用快慢指针，当一个链表有环时，快慢指针都会无限移动下去，并且快指针会追上慢指针，也就是说两个指针相等。

如果fast移动的过程中，fast变为null或者fast.next变为null，那么就不存在环。

这道题的变种可以是求：入环的点，环的长度。这道题只需要判断是否存在环，还比较简单。

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False

876.链表的中间节点

题目链接：https://leetcode.com/problems/middle-of-the-linked-list

解法：

快慢指针。设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次（fast本身是null或者fast.next是null，就没法走了）。

节点数为奇数时，终止循环时，slow就是中间节点。

节点数为偶数时，终止循环时，slow是中间两节点的后一个节点。

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)，slow和fast是常数空间

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        # fast 为 null 终止（偶数情况）
        # fast.next 为 null 终止（奇数情况）
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

125.验证回文串

题目链接：https://leetcode.com/problems/valid-palindrome

解法：

这个题比较简单，唯一注意的地方反而是怎么判断是否为字母或数字。

使用双指针，从两边向中间不断判断即可。

还有空间复杂度为O(1)的写法，不需要事先去掉非字母数字的字符。

边界条件：无

时间复杂度：O(n)

空间复杂度：O(n)

# 空间复杂度为O(1)的写法
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = "".join([c.lower() for c in s if c.isalnum()])
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True