相交链表Java

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 nu11。

以下有两种解决方法:

• 一种是用Map,利用其key值唯一的方法去判断(也可以使用set,set在add时,已存在的元素会返回false,不存在的返回true),但是此种方法会导致额外的空间消耗;
• 另外一种是利用双指针,获取两个链表中的长度,将最长的起始部位和最短的起始部分相等,一起遍历.

    static class ListNode{private int val;private ListNode node;public ListNode(int val, ListNode node) {this.val = val;this.node = node;}@Overridepublic String toString() {return "ListNode{" +"val=" + val +", node=" + node +'}';}}public static void main(String[] args) {ListNode node5 = new ListNode(5, null);ListNode node4 = new ListNode(4, node5);ListNode node3 = new ListNode(3, node4);ListNode node2 = new ListNode(2, node3);ListNode node1 = new ListNode(1, node2);ListNode head3 = new ListNode(3, node3);ListNode head2 = new ListNode(2, head3);ListNode head1 = new ListNode(1, head2);System.out.println("相交链表元素为:" + getIntersectionNode(head1, node1));System.out.println("相交链表元素为:" + getIntersectionNode2(head1, node1));}//相交链表private static ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}int a = 0, b = 0, c = 0;ListNode nodea = headA, nodeb = headB;while (nodea != null) {a++;nodea = nodea.node;}while (nodeb != null) {b++;nodeb = nodeb.node;}nodea = headA;nodeb = headB;if (a < b) {c = b - a;for (int i = 0; i < c; i++) {nodeb = nodeb.node;}} else {c = a - b;for (int i = 0; i < c; i++) {nodea = nodea.node;}}while (nodea != null && nodeb != null) {if (nodea == nodeb)return nodea;nodea = nodea.node;nodeb = nodeb.node;}return null;}private static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {Map<ListNode, Integer> map = new HashMap<>();while (headA != null) {map.put(headA, headA.val);headA = headA.node;}while (headB !=null) {if (map.containsKey(headB)){return headB;}headB = headB.node;}return null;}

相交链表元素为:ListNode{val=3, node=ListNode{val=4, node=ListNode{val=5, node=null}}}
相交链表元素为:ListNode{val=3, node=ListNode{val=4, node=ListNode{val=5, node=null}}}

【LeetCode-160】相交链表_哔哩哔哩_bilibili