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;
		}
	}
}

参考：

1. https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode
2. https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t