第36题：两个链表的第一个公共节点
难易度：⭐⭐⭐⭐
题目描述：
给定ListNode类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
输入两个链表，找出它们的第一个公共结点。
以下内容摘抄自我的文章链表基础题及答案(自己抄自己可还行)
分析：
1：如何判断链表有环无环，如果有环，能否返回第一个入环节点?
image.png
对于一个成环链表，存在这样的规律：
设置一个快指针与一个慢指针，从head出发，如果快指针移动中指向了null则表明这个链表无环，如果有环，则快指针和慢指针迟早会指向同一个节点，本示例中当快指针和慢指针指向的节点重合时为如下场景：
image.png
当快指针慢指针重合时，都指向了标记为橘黄色的节点；此时，快指针回到head处，改成同慢指针一样的一次走一步。快指针和慢指针再次相遇时，指向的节点即为入环的第一个节点，如下所示：
image.png
有了这样的思路，我们就解决了一个链表是否有环，以及它的入环第一个节点是什么的问题。
2：知道两个链表有环无环，以及有环情况时的入环节点后，如何确定两个链表是否相交，如果相交如何确定第一个相交的节点？
共有三种情况：
- 一个链表有环，一个链表无环
对于这种情况而言，两个链表绝对不可能相交
2.两个链表均无环
首先，对两个链表进行遍历，确定每个链表最后一个节点，如果两链表最后一个节点是同一个节点，那么必然相交，然后，我们需要对两链表的长度进行判断，长链表，则先走，走到两链表长度相同时，一直去比对当前节点是否是同一个节点，找到后返回即可。
-
两链表均有环
当两链表均有环时，共有三种情况
一：不相交
image.png
二：相交
image.png
image.png
排除了两种相交的情况，那么两个有环链表则不相交；对于相交情况一而言，我们只需要将链表一从head遍历至入环节点处依次同链表二的如何节点比对即可，对于相交情况二而言，链表一和链表二的入环节点相同，这样一来又变成了无环相交的问题，代码如下：
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null){
return null;
}
ListNode loop1 = getLoopNode(pHead1);
ListNode loop2 = getLoopNode(pHead2);
if(loop1 == null && loop2 == null){
return findNoLoopFirstCommonNode(pHead1,pHead2);
}else if(loop1 != null && loop2 != null){
return findBothLoopFirstCommonNode(pHead1,pHead2,loop1,loop2);
}else{
return null;
}
}
public static ListNode getLoopNode(ListNode node){
if(node == null || node.next == null || node.next.next == null){
return null;
}
ListNode fast = node.next.next;
ListNode cur = node.next;
while(fast != cur){
if(fast.next == null || fast.next.next == null){
return null;
}
fast = fast.next.next;
cur = cur.next;
}
fast = node;
while(fast != cur){
fast = fast.next;
cur = cur.next;
}
return cur;
}
public static ListNode findNoLoopFirstCommonNode(ListNode head1,ListNode head2){
int len1 = 0;
int len2 = 0;
ListNode cur1 = head1;
ListNode cur2 = head2;
ListNode end1 = null;
ListNode end2 = null;
while(cur1 != null){
if(cur1.next == null){
end1 = cur1;
}
cur1 = cur1.next;
len1++;
}
while(cur2 != null){
if(cur2.next == null){
end2 = cur2;
}
cur2 = cur2.next;
len2++;
}
if(end1 != end2){
return null;
}
cur1 = head1;
cur2 = head2;
int n = Math.abs(len1 - len2);
if(len1 > len2){
while(n > 0){
cur1 = cur1.next;
n--;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else if(len1 == len2){
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else{
while(n > 0){
cur2 =cur2.next;
n--;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}
public static ListNode findBothLoopFirstCommonNode(ListNode head1,ListNode head2,ListNode loop1,ListNode loop2){
if(loop1 == loop2){
int len1 = 0;
int len2 = 0;
ListNode cur1 = head1;
ListNode cur2 = head2;
while(cur1 != loop1){
cur1 = cur1.next;
len1++;
}
while(cur2 != loop2){
cur2 = cur2.next;
len2++;
}
cur1 = head1;
cur2 = head2;
int n = Math.abs(len1 - len2);
if(len1 > len2){
while(n > 0){
cur1 = cur1.next;
n--;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else if(len1 == len2){
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else{
while(n > 0){
cur2 =cur2.next;
n--;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}else{
ListNode cur1 = loop1.next;
while(cur1 != loop1){
if(cur1 == loop2){
return loop2;
}
cur1 = cur1.next;
}
return null;
}
}
}
第37题：数字在排序数组中出现的次数
难易度：⭐⭐
题目描述：
统计一个数字在排序数组中出现的次数
本题的最优解是O(logn)的时间复杂度。看到已排序的数组时，我们就应该自然而然地想到二分法，代码如下：
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array == null || array.length == 0){
return 0;
}
int firstK = getFirstK(array,k,0,array.length - 1);
int lastK = getLastK(array,k,0,array.length - 1);
if(firstK != -1 && lastK != -1){
return lastK - firstK + 1;
}
return 0;
}
private int getFirstK(int[] array,int k,int l,int r){
if(l > r){
return -1;
}
int mid = l + ((r - l) >> 1);
if(array[mid] > k){
return getFirstK(array,k,l,mid - 1);
}else if(array[mid] < k){
return getFirstK(array,k,mid + 1,r);
}else if(mid - 1 >= l && array[mid - 1] == k){
return getFirstK(array,k,l,mid - 1);
}else{
return mid;
}
}
private int getLastK(int[] array,int k,int l,int r){
if(l > r){
return -1;
}
int mid = l + ((r - l) >> 1);
if(array[mid] > k){
return getLastK(array,k,l,mid - 1);
}else if(array[mid] < k){
return getLastK(array,k,mid + 1,r);
}else if(mid + 1 <= r && array[mid + 1] == k){
return getLastK(array,k,mid + 1,r);
}else{
return mid;
}
}
}
京公网安备 11010502036488号