LeetCode 解题思路 11（Hot 100）

解题思路：

1. 若相等： 直接返回 true。
2. 若当前元素大于目标值： 由于列递增，当前列下方所有元素均大于目标值，故排除该列（向左移动）。
3. 若当前元素小于目标值： 由于行递增，当前行左侧所有元素均小于目标值，故排除该行（向下移动）。

Java代码：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int i = 0;int j = matrix[0].length - 1; while (i < matrix.length && j >= 0) {if (matrix[i][j] == target) {return true;} else if (matrix[i][j] > target) {j--; } else {i++;}}return false;}
}

复杂度分析：

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

解题思路：

1. 双指针： 两个链表头部同时出发，每次移动一步。当一个链表遍历完后，将其指针重置到另一个链表头部继续遍历。
2. 节点相交： 由于两个链表长度差异会在重置过程中被抵消，最终两个指针必定在相交节点相遇（若存在相交节点）。

Java代码：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode p1 = headA;ListNode p2 = headB;while (p1 != p2) {p1 = (p1 == null) ? headB : p1.next;p2 = (p2 == null) ? headA : p2.next;}return p1;}
}

复杂度分析：

• 时间复杂度： O(m + n)。其中 m 和 n 分别为两个链表的长度。最坏情况下，两个指针各遍历完两个链表一次。
• 空间复杂度： O(1)。仅需常数级的额外空间（两个指针 p1 和 p2）。