【力扣hot100】刷题笔记Day8

前言

到了大章节【链表】了，争取两三天给它搞定！！

160. 相交链表 - 力扣（LeetCode）】

双指针

参考题解，相比于求长度+右对齐再一起出发的方法简洁多了

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB  # A跑完就跳到B开始
            B = B.next if B else headA  # B跑完就跳到A开始
        return A  # 返回重合的节点或者返回空值

206. 反转链表 - 力扣（LeetCode）

双指针

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            temp = cur.next  # 暂存下一个节点
            cur.next = pre   # 反转指针
            pre = cur        # pre后移
            cur = temp       # cur后移
        return pre  # 最后cur是None，pre是最后的结点

234. 回文链表 - 力扣（LeetCode）

快慢指针 + 翻转

参考题解，复用上一题的翻转，注意一下奇偶以及最后要恢复链表

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 翻转链表
        def reverse(head):
            pre, cur = None, head
            while cur:
                temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            return pre
        # 快慢指针
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        pre = slow # 存个pre断点方便恢复
        slow = slow.next  # 后半截从中点的下一个节点开始
        left = head
        right = last = reverse(slow)  # 存个last最后节点方便恢复
        while right:  # 奇数right短一截，偶数right和left一样长
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        # 恢复链表
        pre.next = reverse(last)
        return True