LeetCode Hot 热题100 算法题 160.相交链表-算法&测试-easy模式
程序员文章站
2024-03-22 14:21:28
...
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第169题:多数元素