今天我们一起掌握 leetocode 的 160,169,206 题。

1. lc 160 - 相交链表

  • 题目来源
  • 编写一个程序，找到两个单链表相交的起始节点。
  • 注意：如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
  • 难度：简单

1.1 解题思路 - 哈希表 + 链表

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 bi 是否在哈希表中。若在，则 bi 为相交结点。

复杂度分析

  • 时间复杂度：O(n + m )。
  • 空间复杂度：O(n) or O(m)。 复杂度不符合题目要求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        hashmap = dict()
        move = headA
        while move:
            hashmap[move] = move.val
            move = move.next
        move = headB
        while move:
            if move in hashmap:
                return move
            move = move.next
        return None

1.2 解题思路 - 双指针

初看很难理解，但是换句话理解：A 和 B 两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点；如果A,B不相交的话两个指针就会同时到达A+B和B+A的尾节点。

看到一个关于此题解法的感悟，我悟了：错的人迟早会走散，而对的人迟早会相逢。

复杂度分析

  • 时间复杂度：O(n + m )。
  • 空间复杂度：O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pointer1, pointer2 = headA, headB 
        while pointer1 is not pointer2: # 利用了 None == None , 不相交会跳出
            pointer1 = pointer1.next if pointer1 else headB
            pointer2 = pointer2.next if pointer2 else headA  
        return pointer1

循环必定跳出：

  • 若相交，则返回公共节点；
  • 若不相交，则返回 None；

此外，如果两个链表长度一样，会不会因为在尾部 None = None 跳出，导致没有找到相交点？不会，因为如果一样长，且相交，必定会在尾部之前，在 while pointer1 is not pointer2 的判断下，返回相交点的地址。

2. lc 169 - 多数元素

  • 题目来源
  • 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
  • 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
  • 难度：简单

2.1 解题思路 - 排序

显然排序后，与数组一半以上元素相等的元素，就是答案。

时间复杂度

  • 时间复杂度： O(nlogn)。 将数组排序的时间复杂度为 O(nlogn)。用到了sort()，内部是Timsort算法。
  • 空间复杂度： O(logn)。 如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。

代码

1
2
3
4
5
6
7
8
9
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        mid = len(nums)//2
        return nums[mid]

2.2 解题思路 - Boyer-Moore 投票算法

该解法请查看官方解答。

思路：如果我们把众数记为 +1，把其他数记为 1，将它们全部加起来，显然和大于 0 。

  1. 候选人(cand_num)初始化为nums[0]，票数count初始化为1。
  2. 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
  3. 当票数count为0时，更换候选人，并将票数count重置为1。
  4. 遍历完数组后，cand_num即为最终答案。

为何这行得通呢？ 投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。

因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。

这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。

复杂度分析

  • 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
  • 空间复杂度： O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate, count = nums[0], 0
        for i in range(len(nums)):
            if candidate == nums[i]:
                count += 1
            else: count -= 1
            if count == 0 :
                count = 1
                candidate = nums[i]
        return candidate

3. lc 206 - 反转链表

3.1 解题思路 - 迭代

假设存在链表 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。

3.2 复杂度分析

  • 时间复杂度：假设 n 是列表的长度
  • 空间复杂度：O(n)。

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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 reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return head
        pre, curr  = None, head  
        while curr:  
            curr.next, pre, curr = pre, curr, curr.next # 不要忘记在最后返回新的头引用 `curr.next`！
        return pre