給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 nu11。

以下有兩種解決方法:

• 一種是用Map,利用其key值唯一的方法去判斷(也可以使用set,set在add時(shí),已存在的元素會(huì)返回false,不存在的返回true),但是此種方法會(huì)導(dǎo)致額外的空間消耗;
• 另外一種是利用雙指針,獲取兩個(gè)鏈表中的長(zhǎng)度,將最長(zhǎng)的起始部位和最短的起始部分相等,一起遍歷.

    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