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

2024-01-09 10:44:27

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

文章来源:https://blog.csdn.net/Jack199274/article/details/135470779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。