【算法】求两单链表的第一个相遇点
2022/1/20 1:51:27
本文主要是介绍【算法】求两单链表的第一个相遇点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给定两个可能有环也可能无环的单链表,头节点 head1 和 head2。请实现一个函数,如果两链表相交,请返回相交的第一个节点,不相交返回null。要求:如果两链表长度之和为N,时间复杂度为O(N),额外空间复杂度为O(1)。
题解
- 首先判断两链表有无环,如果有环则求出入环点
- 如果两链表均无环则有以下两种情况
先分别求出两个链表的尾节点,如果不同则不相交。如果相同则设两指针分别指向两链表头节点,长链表的指针先走长度之差步,然后两链表指针同时走,直至相遇,此时指针所指节点即为第一个相遇节点。
- 如果两链表均有环则有以下三种情况
若两链表入环点相同即情况2,则类似与两无环链表情况。计算两链表到入环点的长度之差,长链表的指针先走长度之差步,然后两链表指针同时走,直至相遇,此时指针所指节点即为第一个相遇节点。
若两链表入环节点不同则可能有情况1和情况3。从其中一个链表的入环点开始走,若走完一圈还没碰到另一个链表的入环点则情况1,不相交;若在走完一圈之前碰到了另一个链表的入环点,则为情况3,此时两个入环点均可以是第一个相遇点。
- 如果一个有环一个无环,则必不相交
代码实现
public class FindFirstIntersectNode { //求第一个相交节点,没有返回null public static Node getFirstIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node loop1 = getLoopNode(head1); //求链表1的入环点 Node loop2 = getLoopNode(head2); //求链表2的入环点 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; } Node n1 = head.next; //慢指针 Node n2 = head.next.next; //快指针 while (n1 != n2) { if (n2.next == null || n2.next.next == null) { return null; } n2 = n2.next.next; n1 = n1.next; } n2 = head; while (n1 != n2) { n1 = n1.next; n2 = n2.next; } return n1; } //两链表均无环的情况,返回第一个相交节点,如果不相交返回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; //记录两链表长度之差 while (cur1.next != null) { n++; cur1 = cur1.next; } while (cur2.next != null) { n--; cur2 = cur2.next; } if (cur1 != cur2) { //若尾节点不相等即代表不相交 return null; } cur1 = n > 0 ? head1 : head2; //cur1 变成长链表的头 cur2 = cur1 == head1 ? head2 : head1; //cur2 变成短链表的头 n = Math.abs(n); while (n != 0) { //长链表先走差值步 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; 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 { //入环点不同,从一个入环节点开始走一圈,遇到另一个入环节点即相交 cur1 = loop1.next; while (cur1 != loop1) { if (cur1 == loop2) { return loop1; } cur1 = cur1.next; } //没遇到即不相交 return null; } } //测试节点 class Node{ int value; Node next; } }
这篇关于【算法】求两单链表的第一个相遇点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南