欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

参考:

  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