搜索二维矩阵II
方法：从右上角开始搜索
- 我们可以从矩阵的右上角开始进行搜索。
- 如果当前元素
matrix[i][j]等于target，我们直接返回true。 - 如果
matrix[i][j]大于target，说明target只能出现在左边的列，所以我们将列指针向左移动。 - 如果
matrix[i][j]小于target，说明target只能出现在下方的行，所以我们将行指针向下移动。 - 我们重复这个过程，直到找到目标元素或者行列指针越界。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length == 0 || matrix[0].length == 0){return false;}int m = matrix.length;//行数int n = matrix[0].length;//列数int row = 0;//从第一行开始int col = n-1;//从最后一列开始while(row < m && col >= 0){if(matrix[row][col] == target){return true;}else if(matrix[row][col] > target){col--;//当前元素大于目标，左移}else{row++;//当前元素小于目标，下移}}return false;}
}相交链表
双指针法
-
两个指针分别指向两个链表的头节点：
我们设立两个指针pA和pB，分别指向链表A和链表B的头节点。 -
同时移动两个指针：
- 每次移动一个指针，如果当前指针指向的节点为空，则将其指向另一个链表的头节点。
- 这样做的目的是：让两个指针在遍历完自己的链表后，能够到达另一个链表的头节点，最终相遇的地方就是交点。
-
相遇：
如果两个指针相遇，则返回相遇的节点；如果两个指针同时指向null，则说明链表没有交点。
这种方法的核心思想就是“同步走，互相切换”，确保两个指针走过相同的路程，因此可以在 O(m + n) 时间复杂度内解决问题。
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：
头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。
因此返回 A 即可。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;while(pA != pB){pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;}return pA;}
}反转链表
双指针：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head,pre = null;while(cur != null){ListNode tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}
}回文链表
思路：
- 找到链表的中间节点：使用快慢指针，慢指针每次走一步，快指针每次走两步，最终快指针会指向链表的尾部，慢指针则会指向链表的中间节点。
- 反转后半部分链表：将链表的后半部分进行反转，反转后的链表与前半部分进行比较。
- 比较前后部分：比较反转后的后半部分与前半部分的节点值，如果相同，则该链表是回文链表。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head == null || head.next == null){return true;//链表为空或只有一个元素}ListNode slow = head,fast = head;//快指针走两步，慢指针走一步，直到快指针到达末尾while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}//反转链表的后半部分ListNode secondHalf = reverse(slow);ListNode firstHalf = head;//比较前后部分的节点值while(secondHalf != null){if(firstHalf.val != secondHalf.val){return false;}firstHalf = firstHalf.next;secondHalf = secondHalf.next;}return true;}public ListNode reverse(ListNode head){ListNode prev = null,curr = head;while(curr != null){ListNode temp = curr.next;curr.next = prev;prev = curr;curr = temp;}return prev;}
}环形链表
- 初始化指针：使用两个指针，
slow和fast。slow每次走一步，fast每次走两步。 - 判断是否相遇：如果存在环，
slow和fast会在环内相遇。如果没有环，fast会指向null，即链表的末尾。 - 结束条件：
- 如果
slow和fast相遇，则说明链表有环，返回true。 - 如果
fast到达null，则说明链表没有环，返回false。
- 如果
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null){return false;}ListNode slow = head,fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if(slow == fast){return true;}}return false;}
}环形链表ll
- 使用快慢指针检查链表是否有环。
- 如果有环，重新定位慢指针到头节点，同时让慢指针和快指针都以相同的速度（每次一步）向前走，直到它们相遇。
- 相遇的节点就是入环的第一个节点。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){return null;}ListNode slow = head,fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if(slow == fast){//找到环的起点ListNode pointer = head;while(pointer != slow){pointer = pointer.next;//pointer从头节点开始走slow = slow.next;//slow从相遇点开始走}return pointer;}}return null;}
}
