当前位置：网站首页>算法拾遗十五补链表相关面试题
算法拾遗十五补链表相关面试题
2022-08-05 06:26:00 【lsd＆xql】
判断链表是否相交
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
【要求】 如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
思路：
首先解决有环及无环的问题：如果无环返回空，如果有环返回第一个入环节点。
下图框起来的则是第一个入环节点：
首先通过容器的办法解决这个问题，准备一个HashSet保留所有经过的节点，每经过一个节点都判断一下
是否存在于HashSet里面。
其次深入不用容器的方法（关键在于如何找到第一个入环节点）：准备一个快指针（一次走两步）以及一个慢指针（一次走一步），如果快指针提前走到空了，那么肯定是一个无环的单链表，那么快慢指针肯定会相遇，
当相遇了之后将快指针移动到头节点，然后慢指针和快指针每次都走一步，相遇的位置就是第一个入环节点。
在上图点上S与F相遇了（S代表慢指针，F代表快指针）。
接下来F回到开头，变成一次只走一步
S和F都走两步，相遇的点就是第一个入环节点。
同理如下边界条件也是成立的F回到头节点，而S则在那个环点上一直循环
代码如下：
// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head) {
//提前判断是否有三个点
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
//如果快慢指针没有相遇则一直循环
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
接下来找到两个链表的第一个入环节点（loop1和loop2）
1、如果都为空，则考虑两个无环的单链表该如何判断相交（类似于Y）
如果有容器的话则用hashSet取出对应节点的内存地址
Integer.toHexString(obj.hashCode())
如果没有容器，从链表1出发找到第一个end1，找到长度len1
从链表2出发找到end2，如果end1的内存地址和end2的内存地址不相等，则这个链表
肯定不相交【end1和end2是相交的最后一个节点】
那么如何求得相交得第一个节点呢？
方式：
如果链表1是100个节点，链表2是80个节点，先让链表1先迈20步，然后再让链表1和链表2
一起走，则他们一定会在第一个相交得节点处相遇（因为end都是一样得只是长度不一样）
代码如下：
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
//如果n为正数链表1长，负数链表2长
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
//如果内存地址不一样则不相交
if (cur1 != cur2) {
return null;
}
// n : 链表1长度减去链表2长度的值
cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
//cur1保存长链表的头，cur2保存短链表的头
n = Math.abs(n);
while (n != 0) {
n--;
//然后让长链表向后移动n步
cur1 = cur1.next;
}
//长链表以及短链表一起走，直到相遇
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
2、分为一个链表有环和一个链表无环
注：这种情况不可能相交（因为要相交肯定会造成两个链表成环的），如果一个链表不成环
的话那么肯定不是相交的
3、两个链表都有环（loop1和loop2都不为空）
（1）两个环各自独立不相交
（2）统一理解为head1和head2入环节点是同一个
（3）这里入环节点不是同一个
这样就可以得出结论如果loop1等于loop2则是第二种情况，但是怎么求相交呢，则可以
认为两个链表分别以loop1和loop2结尾，然后两个无环链表求交点。
如果loop1不等于loop2，则要么是情况1要么是情况3，则从loop1开始走一圈看能否与
loop2相遇，如果相遇了则是情况3，如果没有相遇则是情况1。
代码如下：
// 两个有环链表，返回第一个相交节点，如果不想交返回null
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
//情况2，跟之前的无环链表相交一样
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
//情况1或者情况3
cur1 = loop1.next;
//loop1开始往下循环找，如果在第一次循环的过程中找到loop2了，
//那么则返回当前的交点，如果第一次循环结束了那么说明没有交点返回null
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
整体代码如下：
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head) {
//提前判断是否有三个点
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
//如果快慢指针没有相遇则一直循环
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
//如果n为正数链表1长，负数链表2长
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
//如果内存地址不一样则不相交
if (cur1 != cur2) {
return null;
}
// n : 链表1长度减去链表2长度的值
cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
//cur1保存长链表的头，cur2保存短链表的头
n = Math.abs(n);
while (n != 0) {
n--;
//然后让长链表向后移动n步
cur1 = cur1.next;
}
//长链表以及短链表一起走，直到相遇
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
// 两个有环链表，返回第一个相交节点，如果不想交返回null
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
//情况2，跟之前的无环链表相交一样
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
//情况1或者情况3
cur1 = loop1.next;
//loop1开始往下循环找，如果在第一次循环的过程中找到loop2了，
//那么则返回当前的交点，如果第一次循环结束了那么说明没有交点返回null
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
总结
能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉?
抖机灵的做法：给出要删除的结点，把该节点的next赋值给该节点，然后让该节点跨过下一个结点，让next指针指向下下一个节点其实这样本质上并没有把自己删除掉，除此之外，尾巴结点删除不掉
边栏推荐
猜你喜欢
随机推荐
Get the network input dimensions of the pretrained model
Detailed explanation of the construction process of Nacos cluster
Redis的使用
亚马逊美国站：马术头盔CPC认证标准要求
淘宝宝贝页面制作
typescript64-映射类型
Promise (3) async/await
Writing OpenCV in VSCode
【8】Docker中部署Redis
golang-条件语句
2022杭电多校六 1006-Maex （树形DP）
工作3年，回想刚入门和现在的今昔对比，笑谈一下自己的测试生涯
【C语言】结构体变量数据通过 void* 传入到函数中
七夕！专属于程序员的浪漫表白
LaTeX uses frame to make PPT pictures without labels
文本样式这一篇文章就够了
盒子模型小练习
小程序input框不允许输入负数
Unable to import torchvision. IO. Read_image
protobuf根据有关联的.proto文件进行编译