当前位置：首页 > news >正文

LC-搜索二维矩阵II、相交链表、反转链表、回文链表、环形链表、环形链表ll

news 来源：原创 2025/9/21 14:34:35

搜索二维矩阵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;}
}