LeetCode Hot100-Day 2

Created by: Yuanpeng QU
Created time: 2025年8月15日 14:37

2. 两数相加[mid]

给定两个链表l1，l2，表示逆向储存的数字，比如1→2→3表示321，求两个链表表示的数字相加的和的链表，两个链表的长度可以不一样，每个节点的值不超过10。

实际上逆向储存的意思就是刚好按照个十百千这个顺序来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode()
        current = dummy_head
        carry = 0 # 进位

        while l1 or l2 or carry:
          l1_val = l1.val if l1 else 0
          l2_val = l2.val if l2 else 0

          # 个位开始相加(包含上一位的进位)
          sum_ = l1_val + l2_val + carry
          d = sum_ % 10
          carry = sum_ // 10

          current.next = ListNode(d) #第一次创建的话就是在dummy.next
          current = current.next

          if l1:
            l1 = l1.next
          if l2:
            l2 = l2.next

        return dummy_head.next

  • 关键思路：明白逆向的意义，以及知道储存相加导致的进位carry

  • 不知道的话就会想到将链表读取值后转成数组，再转成数字，相加后再转换回链表，这样复杂度爆炸，因为如果链表长度特别长的话运行时间肯定超

  • 知道逆向存储是按照个十百千这个顺序的话，还需要再知道一个关键：

    num % 10 ⇒对任意一个数取余数，比如7%10=7, 12%10=2，就能得到其个位数是什么

    num // 10 ⇒对任意一个数取10位数的值，可以表示要进几位，比如7//10=0,17//10=1

    这样任意一个数就能通过num%10 num//10-拼在一起得到

  • 开始的时候先定一个哑巴指针dummy让curr指向它，最后dummy.next指向的链表作为输出。

  • while l1 or l2 or carry：只要其中有不为0或none的话就还需要继续算，先取出l1和l2第一个节点的值，也就是个位数将他们和carry相加，得到结果，因为是个位所以carry=0不会造成进位，然后求出现在这个数的值(%10)和是否需要进位(//10)，将这个值存到curr.next上，而cur.next还没被创建，也就是得先创建新节点用来存值，再将cur指向新节点的next，最后再把l1和l2向后移一位(要判断下一位是否为空)

19. 删除链表的倒数第 N 个结点[mid]

1→2→3→4→5 n=2 ⇒ 1→2→3→5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(0,head)
        current = head
        size = 0
        while current:
          current = current.next
          size += 1

        p = size - n
        current = head
        
        if p == 0:
          head = head.next
          return head
        
        for _ in range(p-1):
          current = current.next
        current.next = current.next.next
        return dummy_head.next
  • 最直观的想法：先计算链表的长度size，再通过size-n得到需要删除的节点所在的正向顺序，然后再遍历一遍链表到这个位置的前一个节点，将这个节点的nextnext指向删掉的节点的next，这样就删掉了。
  • 注意如果size-n==0，也就是说是head节点被删了，就需要head.next赋给现在的head，这样原来的head就删了。

21. 合并两个有序链表[easy]

两个值从小到大排列的链表合并成一个，合并完的链表仍然是从小到大排序的

1→2→3→4→5

1→3→4→4→8

1→1→2→3→3→4→4→4→5→8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(0)
        current = dummy_head

        while list1 and list2:

          if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
          else:
            current.next = list2
            list2 = list2.next

          current = current.next
        if list1:
          current.next = list1
        else:
          current.next = list2

        return dummy_head.next

  • 关键点：有序链表，可以把两个链表的节点比较大小后像拉链一样一个一个塞到新链表里
  • 一般需要新建链表的时候都会提前初始化一个dummy_head=ListNode(0)，然后让它指向我们最后要返回的链表。
  • 只要list1和list2都不为空才需要比较大小，如果有一个为空的话另一个不为空的显然要比所有的值都要大，因为是递增链表。这样的话直接将剩下的值拼接到合并的链表最后面就完成了。
  • 比大小则是current指向新链表，然后将值小的节点放到current指的位置，current往后移，如此重复。

141. 环形链表[easy]

判断一个链表有没有环，有就返回true，其中pos只是告诉你例题中环的所指位置

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False
  • 核心思想：运动场跑道上跑得快和跑得慢的人同时从起点出发，跑得快的人肯定会在某圈后和跑的慢的人相遇
  • 直接创建一个fast和slow指针指向head，fast每次遍历两个节点，slow遍历一个，这样如果没有环的话fast肯定先到末尾，fast.next会指向none，以及fast自己也可能是none，这样就能作为while的停止条件了，而如果有环的话肯定会有一个时间点有fast == slow，这个时候返回true

142. 环形链表 II[mid]

和141一样，但是要求第一次遇到环的时候环的起点位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import collections

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        hashmap = set()
        current = head
        while current:
            if current in hashmap:
                return current
            hashmap.add(current)
            current = current.next

        return None
  • 解法一还是弗洛伊德法，也就是141的方法，最高效O（1）但是难懂，我选择解法二，也就是哈希表查表秒杀
  • 关键：哈希表不能用带默认值int的，因为链表和数组不一样没法确定节点index，所以set()才是最好的，也就是说循环遍历链表的同时将节点整个加入set中（add），然后同时判断set里面有没有重复的节点，有的话直接返回，没有的话循环到最后肯定会跳出，也就是current.next最后肯定是none，返回false即可。

160. 相交链表[easy]

给定两个链表，判断他们到那个节点会相交，相交后成为一个链表，也就是【Y】逆时针90度的样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None

        pA = headA
        pB = headB

        while pA != pB:
            if pA is None:
                pA = headB
            else:
                pA = pA.next
            if pB is None:
                pB = headA
            else:
                pB = pB.next

            # 简洁版：
            # pA = pA.next if pA else headB
            # pB = pB.next if pB else headA
        
        return pA
  • 核心思路：一个指针从走完A链表再走B链表 == 另一个指针走完B链表再走A链表，如果他们有交点，那到最后两指针走的路肯定相等，并且最后的交汇处就是交点：假如AB链表相交后的链表为C，那就有指针1的路径A+C+B，指针2的路径B+C+A,显然这两个路径是相等的，并且都走到底后就该走C了，他们会相交。如果没有交点的话他们不相交，最后两个指针的值肯定都是none。注意while的条件就是他们不相交就一直遍历，如果不相交最后也会因为都是none而跳出循环。
  • 或者用哈希表存A链表的每一个节点也可以，再遍历B，遍历的时候去哈希表里查有没有和A重复，重复的第一个节点就是相交节点，直接返回

206. 反转链表[easy]

将给定链表反转

两种方法都常考，分别是指针法和递归法

  • 指针法可以把链表想象成火车，A→B→C→D，现在对B施工（current）想将它的车头和车尾调过来，第一步就是先把B前头的牵引B→C系上安全绳（tmp = current.next）防止前面的车厢丢了，第二步就可以将牵引接到A上了（current.next = prev），完事后需要到下个车厢C去继续调转车头车尾，需要从B“过去”，B车厢则是之前的工作地(current = prev)此时current还是B车厢，最后我们到了C车厢，C车厢则成为现在的工作地（current = tmp）
  • 原链表:1→2→3→4(pre=null)
    1: null←1 2→3→4(pre=1)
    2: null←1←2 3→4(pre=2)
    3: null←1←2←3 4(pre=3)
    4: null←1←2←3←4(pre=4)
1
2
3
4
5
6
7
8
9
10
prev = None
current = head

while current:
    tmp = current.next
    current.next = prev
    prev = current
    current = tmp

return prev # 返回的是prev！！！！
  • 递归法：利用head和head.next==None的条件来递归调用自己
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if head is None or head.next == None:
            return head # 链表为空或者只有一个节点直接返回本身,同时作为递归停止条件
        
        newHead = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return newHead
  • 假如要反转1→2→3，那么递归法首先会执行到newHead = self.reverseList(head.next), 其中head==1，所以head.next==2，把2作为head再调用自己一次，此时的newHead = self.reverseList(1)暂停，等待递归结果返回，现在进入newHead = self.reverseList(2)，
  • 2里面同样不满足if的递归停止判断，来到newHead = self.reverseList(2.next) 也就是 self.reverseList(3)，到了 self.reverseList(3)，满足了if条件，return head==3，这下 self.reverseList(2)等到了返回的结果也就是newHead = 3，但是在 self.reverseList(2)中head还是2，head.next == 3,
  • 我们直接反转链表，也就是将head.next.next = 2，也就是将3的next直接设为2（这个时候head还是2，而newhead才是3），就是当前节点这样就出现了1 -> 2 <-> 3，2和3双头都链接了，需要断掉2→3这个链子，所以下一步就是head.next = None也就是2.next = none，结果就是1 -> 2 <- 3，return newHead回去self.reverseList(1)，相同操作就能得到null←1←2←3了,最后返回的头节点就是newHead==3

24. 两两交换链表中的节点[mid]

将一个链表里的元素两两分别交换：1-2-3-4 ⇒ 2-1-4-3

  • 方法一，迭代法，基本就是三个指针两两交换，但是这里最关键也是最方便理解的是设定一个prev指针指向head，并且以prev的视角来交换节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(0,head)
        prev = dummy_head
        while prev.next and prev.next.next:
            node1 = prev.next
            node2 = prev.next.next
						
						# prev->1->2->3->4  前后两个链不能断，也就是prev.next和node2.next
            prev.next = node2
            node1.next = node2.next
            node2.next = node1
            prev = node1

        return dummy_head.next
  • 首先需要设置一个dummy_head用来输出变化完后的整个数组，然后再设置一个prev指向head
  • 条件是while prev.next和prev.next.next 都不为none，当然可以设值current，但是这里以prev的视角来会更简单。并且设node1=prev.next, node2=prev.next.next
  • 接下来开始迭代的经典操作，prev.next = node2 , node1.next = node2.next, node2.next = node1注意，这三个顺序是可变的，关键在于有没有错误的把后面的链接断掉。最后将prev移动到node1：prev = node1进行下一轮while
  • 递归法暂时先不看，并且递归法空间复杂度高一点

25. K一个组翻转链表[hard]

给定一个链表和一个k，将链表按长度为k的子链表进行划分，再将每个子链表内部进行翻转，如果划分到最后长度不够k则这部分不用翻转。 1→2→3→4→5, k=2 ⇒ 2→1→4→3→5

这题主要分3步，1.按k划分 2.子链表内部翻转 3.翻转后的结果拼接到原来链表上

  • 所以先考虑怎么按k来划分。把长度为k的子链表看成一个整体节点的话，对于这个整体我们需要它前面的指针（group_prev）和后面的指针（group_next）,然后还有指向它自己的指针kth
  • 所以使用dummy_head方便表示边界和输出，并且将group_prev和他一样指向头部节点。接下来就是遍历链表到k的位置，如果链表的长度不够k则没法翻转任何地方，所以直接跳出，返回。这里的关键是kth = group_prev，kth也从头节点的前一个开始，这样for循环遍历完后kth就会在这一子链表的最后一个节点。同样第二个关键则是还需要判断一次 if kth is None:
  • 最关键的就是kth到位后，需要把现在的子链表和链表的后续节点链接起来，这样才不会丢失后续节点，也就是 group_next = kth.next。同样也需要保存最开始的节点这样能够在翻转完后能够将开始节点链接到后续节点head_of_group = group_prev.next，因为翻转后它就成子链表的最后节点了。此时group_next指向后续节点，group_prev指向子链表第一个节点前面的节点。
  • 接下来开始翻转子链表，关键在于需要用到prev和curr专门来对翻转子链表进行操作。（和206题一样）此时prev = group_next(不同于206，因为206反转完后最后一个节点前面是null，而这题前面则是下一组的第一个节点)，curr = group_prev.next
  • 翻转子链表内容就和206完全一样，想象一个火车的车厢对调，先系安全绳：next_tmp = curr.next, 然后翻转当前车厢: curr.next = prev, 翻转完成后需要移动到下一个车厢继续，所以现在的上一个车厢则成了刚才施工的车厢：prev = curr, 现在的车厢在哪？在安全绳的后面: curr = next_tmp。
  • 完成后的关键就是拼接回后续链表（和前面的链表）上，也就是将kth所指位置给到group_prev的next上，这样就能把上一组的末尾节点通过group_prev链接到刚刚翻转完成的这一组的头节点上：group_prev.next = kth（kth在翻转前是这一组的最后面，翻转后就到最前面了，要将前面一组的头部节点和它链接）, 然后就是链接后面节点，head_of_group本来是这组的头节点，翻转完后就到最后一个节点了（下一组的前面一个节点），通过这个公式将group_prev 链接到下一组的前面一个节点：group_prev = head_of_group，注意不能把上面这两个公式一块看，要分开看。至此结束，循环结束后返回dummy_head.next就能得到整个链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: Optional[ListNode]
        :type k: int
        :rtype: Optional[ListNode]
        """
        if head is None or k == 1:
            return head
        
        dummy_head = ListNode(0, head)
        group_prev = dummy_head
        while True: #
            kth = group_prev #
            for _ in range(k): #
                if kth is None:
                    break
                kth = kth.next
            
            if kth is None:
                break
            
            group_next = kth.next
            head_of_group= group_prev.next #

            prev = group_next
            curr = group_prev.next

            for _ in range(k):
                next_tmp = curr.next
                curr.next = prev # 
                prev = curr
                curr = next_tmp

            group_prev.next = kth #
            group_prev = head_of_group #
        
        return dummy_head.next