可以自己做效果图的网站,泉州网红餐厅,3g手机网站源码,百度指数关键词问题概述
单链表定义如下#xff1a; public class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}}编写程序#xff0c; 找出两个链表的交点。 如图所示#xff0c;链表 A 和链表 B 在节点 8 处相交。
算法思路
首先确定一个事情#xff1a; …问题概述
单链表定义如下 public class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}}编写程序 找出两个链表的交点。 如图所示链表 A 和链表 B 在节点 8 处相交。
算法思路
首先确定一个事情
如果两个链表有交点 那么这两个链表的尾节点一定是相等的。现在不仅需要判断是否有交点 还需要找出这个节点。继续观察图形 可以得出如果两个链表相交那么较长链表在往后移动 (∣length1−length2∣|length1-length2|∣length1−length2∣)个长度单位后两个链表往后查找的速度一致即可以用判断两个节点是否相等的方式来判断交点的位置了。 代码实现
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headAnull||headBnull) {return null;}int l1 getListNodeLength(headA);int l2 getListNodeLength(headB);boolean aLargerThanB l1l2;//可以知道两个链表的长度int abs aLargerThanB?(l1-l2):(l2-l1);if (abs!0) {if (aLargerThanB) {while(abs0) {headA headA.next;abs--;}}else{while(abs0) {headB headB.next;abs--;}}}while (headA!null) {if (headAheadB) {return headA;}headA headA.next;headB headB.next;}return null;}public int getListNodeLength(ListNode head) {int length 0;while(head!null) {length;head head.next;}return length;}
