LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2551字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式](/upload/InfoBanner/zyjiaocheng/615/12e35760802645a4bf1c179ad9c6bf15.jpg)
LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式
编写一个程序,找到两单链表相交的起始节点。
输入:listA=[1,2,3,4,5] listB=[0,3,4,5] intersectVal=5
输出:value=5
package leetcode.easy;
import java.util.HashSet;
import java.util.Set;
//160.相交链表
public class Solution160 {
public static void main(String[] args) {
//链表1
ListNode head1=new ListNode(1);
ListNode curr1=head1;
curr1.next=new ListNode(2);
ListNode intersect = new ListNode(3);
curr1.next.next = intersect;
intersect.next = new ListNode(4);
intersect.next.next = new ListNode(5);
//链表2
ListNode head2=new ListNode(0);
ListNode curr2=head2;
curr2.next=intersect;
//是否相交
S160IntersectLinkedList testIntersectLinkedList = new S160IntersectLinkedList();
System.out.println(testIntersectLinkedList.getIntersectionNode(head1,head2).val);
}
}
class S160IntersectLinkedList{
//两链表从相交节点到末尾的长度一样,从头节点到相交节点的长度可能不同
//让两个指针都在距末尾相同距离处开始遍历,即短链表的头节点处
//消除两链表的长度差:
//1.p1指向链表1,p2指向链表2,从头开始遍历
//2.如果p1到了末尾 则p1=head2,继续遍历;
//3.如果p2到了末尾 则p2=head1,继续遍历
//4.当较长链表指针指向较短链表的head时,已消除长度查
//5.遍历两链表,直到找到相同节点 或null
public ListNode getIntersectionNode(ListNode head1,ListNode head2) {
ListNode p1 = head1;
ListNode p2 = head2;
if (head1==null || head2==null) {
return null;
}
while(p1!=p2) {
// if (p1==null) {
// p1=head2;
// }else {
// p1=p1.next;
// }
// if (p2==null) {
// p2=head1;
// }else {
// p2=p2.next;
//
// }
p1 = p1==null ? head2 : p1.next;
p2 = p2==null ? head1 : p2.next;
}
return p1;
}
//法2:需要额外空间
//没找到相交节点返回-1,找到则返回节点的值
public int intersectionNode(ListNode l1,ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
Set<Integer> list1 = new HashSet<Integer>();
//将链表1的节点值加入hashset中,遍历链表2,看是否有相同的值
while(cur1!=null) {
list1.add(cur1.val);
cur1=cur1.next;
}
// System.out.println(list1.toString());// list1: [1, 2, 3, 4, 5, 6]
// Set<Integer> list2 = new HashSet<Integer>();
// while(cur2!=null) {
// list2.add(cur2.val);
// cur2=cur2.next;
// }
// System.out.println(list2.toString());//list2: [0, 3, 4, 5, 6]
while(cur2!=null && !list1.contains(cur2.val)) {
// System.out.println(cur2.val+" no");
cur2=cur2.next;
}
if (cur2==null) {
return -1;
}else {
return cur2.val;
}
}
}
参考:
- https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode
- https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t
内容总结
以上是互联网集市为您收集整理的LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式全部内容,希望文章能够帮你解决LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。