题目

给定一个 m x n 的矩阵 matrix，请编写一个高效的算法来判断目标值 target 是否存在于矩阵中。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

---

示例 1

输入：
matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
target = 5

输出：
true

解释：
目标值 5 存在于矩阵中。

---

示例 2

输入：
matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
target = 20

输出：
false

解释：
目标值 20 不存在于矩阵中。

---

提示

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列。
• 每列的所有元素从上到下升序排列。
• -10^9 <= target <= 10^9

实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr) return nullptr;

        // 让两个指针走以一样长的路
        ListNode* work1 = headA , *work2 = headB;
        while(work1 != work2) {
            work1 = work1 == nullptr ? headB : work1 -> next;
            work2 = work2 == nullptr ? headA : work2 -> next;
        }
        return work1;