剑指 Offer（第 2 版）

记录刷剑指题目

剑指 Offer 03. 数组中重复的数字

数组中重复的数字 【哈希表】

class Solution:
    def findRepeatNumber(self, nums) -> int:
        dic = set()
        for num in nums:
            if num in dic:
                return num
            dic.add(num)
        return -1

剑指 Offer 05. 替换空格

替换空格

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in s:
            if i == " ":
                res.append("%20")
            else:
                res.append(i)
        return "".join(res)

剑指 Offer 24. 反转链表

反转链表

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


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = None
        while head:
            cur = head.next  # 抓手
            head.next = pre  # 反转
            pre = head
            head = cur      # 往下走
        return pre

剑指 Offer 25. 合并两个排序的链表

合并两个排序的链表

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode):
        if list1 is None or list2 is None:
            return list2 if list1 is None else list1

        head = ListNode(0)

        if list1.val <= list2.val:
            head = list1
        else:
            head = list2

        cur1 = head.next
        if head == list1:
            cur2 = list2
        else:
            cur2 = list1
        pre = head
        while cur1 and cur2:
            if cur1.val <= cur2.val:
                pre.next = cur1
                cur1 = cur1.next
            else:
                pre.next = cur2
                cur2 = cur2.next
            pre = pre.next
        if cur1:
            pre.next = cur1
        else:
            pre.next = cur2
        return head

剑指 Offer 58 - II. 左旋转字符串