【力扣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
    

后言

• 在工位刷题效率杠杠的！有双屏无论是编辑博文还是看题解都很舒服~ 链表真好玩呀（