阿里巴巴电子商务网站,廉江市住房和城乡建设局网站,广东装饰网站建设,wix英文网站建设给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点#xff0c;返回 nu11。 以下有两种解决方法:
一种是用Map,利用其key值唯一的方法去判断(也可以使用set,set在add时,已存在的元素会返回false,不存在的返回…给你两个单链表的头节点 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) {MapListNode, 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{val3, nodeListNode{val4, nodeListNode{val5, nodenull}}} 相交链表元素为:ListNode{val3, nodeListNode{val4, nodeListNode{val5, nodenull}}} 【LeetCode-160】相交链表_哔哩哔哩_bilibili
