建设部四库一平台查询网站,推广网络公司,网站建设低价建站损失在哪里,做网站要注册公司吗力扣题目链接 思想#xff08;数学#xff09;#xff1a;设链表A的长度为a#xff0c;链表B的长度为b#xff0c;A到交点D的距离为c#xff0c;B到交点D的距离为d。显然可以得到两者相交链表的长度为#xff1a;a - c b - d ,变换一下式子得到#xff1a;a d b c…力扣题目链接 思想数学设链表A的长度为a链表B的长度为bA到交点D的距离为cB到交点D的距离为d。显然可以得到两者相交链表的长度为a - c b - d ,变换一下式子得到a d b c.
用一个指针从链表A出发走完后接着从链表B出发另一个指针从链表B出发走完后接着从链表A出发。若两个链表相交当前一个指针走了a d步时此时后一个指针走b c步即走到了交点。若两个链表不相交两个指针最终都会走向NULL
总的来说是让双指针一个指针走一遍A再走B。另一个指针走一遍B再走A。当两个指针走第二个链表时相等的点即为交点。若无交点 两个指针最终都为NULL
代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode t1 headA, t2 headB;while (t1 ! t2) {t1 t1 ! null ? t1.next : headB;t2 t2 ! null ? t2.next : headA;}return t1;}
}思路非数学注意本题是找两个链表的交点即两个节点是相同的而不是简单的值相等。如果找到交点那么两个链表后面的节点一定是一样的因为他们是通过next指针连接起来的。
即如果找到两个链表相等的节点那么就直接返回这个节点即可后面的节点就无需再比较了一定是相等的。
暴力解法是遍历链表A每遍历一个节点再遍历链表B看是否有相等的节点如果有直接返回此节点即可。如果没有继续循环。时间复杂度为0n*m
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode t1 headA;while (t1 ! null) {ListNode t2 headB;while ( t2 ! null) {if (t1 t2) return t1;t2 t2.next;}t1 t1.next;}return null;
}
}法三首先遍历两个链表求出长度。然后求出两个链表长度的差值让长的链表向后走差值步让两个链表对齐。然后同时两个链表同时向后走如果有相同的节点即找到交点直接返回。时间复杂度为On m 代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a headA, b headB;int s1 0, s2 0;while (a ! null){a a.next;s1 ;}while (b ! null) {b b.next;s2 ;}a headA;b headB;if (s2 s1) {//交换链表int temp s1;s1 s2;s2 temp;ListNode tempNode a;a b;b tempNode;}int gap s1 - s2;while (gap -- 0) { //走到与b同一起点a a.next;}while (a ! null) {if (a b) return a;a a.next;b b.next;}return null;
}
}
